The edit distance, also known as Levenshtein distance, between two words is the minimum number of substitutions, insertions and/or deletions required to change one word into another. An (n, M, d)_q edit code is a q-ary code with minimum edit distance d and in which the longest codeword has length n. A code is optimal if it has the maximum number of codewords for any code with a given maximum length and minimum distance. We explore the idea of using families of well-known Hamming distance codes as a starting point for construction of edit distance codes. For some small parameter sets these can produce provably optimal edit codes. For larger parameter sets where a brute force approach is infeasible, we use the Hamming distance codes as an initial population for a Genetic Algorithm. While these techniques cannot guarantee an optimal code, they do create optimal codes in some cases, and provide reasonable lower bounds for other larger cases for which this was previously infeasible.
展开▼
