字符串是无处不在，模棱两可。 建立沟通渠道时，不可避免的噪音和误解，可以引入文本数据传输中的错误。
在企业系统中，有许多地方可能会发生这种类型的错误。 客户名称，地址，公司名称，等等。 这种类型的错误可能使不切实际的查询记录的。 想象一下，著名演员阿诺德·施瓦辛格的动作片的悲惨生活，他有他的名字拼写为运营商多次？
要解决这个问题，创造了一些算法搜索紧密联系起来的话，其中有拼音的算法。 算法使用字符串转换成音素的语音规则，试图统一类似冠冕堂皇的话。 算法的例子：
但所有这些算法遭受同样的问题。 书面规则是专门为特定的语言，和大多数实现英语作为目标语言。 这不是一个问题，如果你的系统是讲英语的用户，你是不是有兴趣在各种语言的应用... 因为这个世界日益全球化，我觉得它是很难的情况下......
但也有其他的解决方案？ 好消息！ 寻找替代品，我想的话，搜索算法近似编辑距离的类别，特别是Levenshtein距离算法 。 更加稳定可靠，可用于任何程序员在任何语言没有改变。 甚至一个小的优势：它不仅会返回一个布尔响应，说这是成功与否不是在搜索，但一个数字，告诉多么相似的两个词，这使得它可以排序候选人的集合，其从地面的距离要求。 这个小的优势，可以是页面之间和页面结果没有任何价值，或与最相关的结果的第一有序列表的区别。
Levenshtein距离的算法，它被命名后，它的创造者，俄罗斯的弗拉基米尔·Levenshtein ，计算成本转化成另一种的话，假设某些操作，如插入，删除或替换字符。 可以描述如下：
是自己和SJ字符串的字符我，j的整数，0 <= I <=大小（自我）和0 <= J <=大小（J）。 D（BS，SJ）函数的计算本身和SJ之间的编辑距离。
（SI）的长度是等于0，那么d（BS，SJ）=长（SJ）。 反过来持有SJ。
如果你和SJ是不是空字符串，那么可以写为SI = SJ = sj'c2 si'c1，其中C1是自己的最后一个字符，C2是SJ的最后一个字符。 如此这般：
如果C1 = C2，则显然D（SI，SJ）= D（SI，SJ“）。
如果c1 = c2，那么d（BS，SJ）= MIN（1 + D（BS，sj'c2），1 + D“（si'c1，SJ”），1 + D（BS“SJ”） ）= 1 +（最低D（BS“，sj'c2），D（si'c1，SJ”），D（BS'，SJ“））
最后一行应该有自己的解释。 如果C1是C2不同，然后本身和SJ之间的编辑距离是最小的操作被删除本身C1，C2或删除律政司司长，我们相信，我们更换或C1到C2（或反之亦然。）
正如你可以看到，这给了我们一个美丽的递归算法，也可以用Java编写的：
static int levenshtein(String si, String sj) {
return d(si, si.length() - 1, sj, sj.length() - 1);
}
static int d(String si, int i, String sj, int j) {
if (i == -1) {
return j + 1;
}
if (j == -1) {
return i + 1;
}
if (si.charAt(i) == sj.charAt(j)) {
return d(si, i - 1, sj, j - 1);
}
return 1 + min(d(si, i - 1, sj, j), d(si, i, sj, j - 1), d(si, i - 1, sj, j - 1));
}
static private int min(int i1, int i2, int i3) {
return Math.min(Math.min(i1, i2), i3);
}
Apesar de achar o algoritmo recursivo mais fácil de entender e implementar, infelizmente ele é muito ineficiente. Se acompanhamos a execução para duas cadeias quaisquer, vemos que são calculadas solução para as mesmas subcadeias repetidas vezes. Por exemplo, ao calcular a distância entre as palavras "gente" e "gene" (distância 1), vemos a seguinte pilha de execução:
Calculando distância entre gene e gente
Calculando distância entre gen e gent
Calculando distância entre ge e gent
Calculando distância entre g e gent
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre ge e gen
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre ge e ge
Calculando distância entre g e g
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre gen e gen
Calculando distância entre ge e ge
Calculando distância entre g e g
Calculando distância entre ge e gen
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre ge e ge
Calculando distância entre g e g
Calculando distância entre g e ge
Calculando distância entre g e g
Distancia 1
Relembrando as aulas de algoritmos da faculdade, podemos ver que este algoritmo possue algumas características importantes: substrutura ótima (a solução ótima contêm soluções ótimas para subproblemas), os subproblemas são independentes e o espaço de subproblemas é tão reduzido que o algoritmo recursivo está o tempo todo resolvendo os mesmos problemas. Terreno fértil para o uso de técnicas de programação dinâmica.
Uma das técnicas mais conhecidas é o da memoização. Simplificando, trata-se simplesmente em construir uma tabela com os resultados parciais assim que são calculados, evitando com isso os recalculos desnecessários. Alterando a implementação recursiva anterior utilizando esta técnica, ficaria:
private static int[][] mem;
static int levenshtein(String si, String sj) {
mem = new int[si.length()][sj.length()];
for (int i = 0; i < si.length(); i++) {
for (int j = 0; j < sj.length(); j++) {
mem[i][j] = -1;
}
}
return d(si, si.length() - 1, sj, sj.length() - 1);
}
static int d(String si, int i, String sj, int j) {
if (i == -1) {
return j + 1;
}
if (j == -1) {
return i + 1;
}
if (mem[i][j] > -1) {
return mem[i][j];
}
if (si.charAt(i) == sj.charAt(j)) {
mem[i][j] = d(si, i - 1, sj, j - 1);
return mem[i][j];
}
mem[i][j] = 1 + min(d(si, i - 1, sj, j), d(si, i, sj, j - 1), d(si, i - 1, sj, j - 1));
return mem[i][j];
}
static private int min(int i1, int i2, int i3) {
return Math.min(Math.min(i1, i2), i3);
}
O que nos dá a seguinte pilha de execução:
Calculando distância entre gene e gente
Calculando distância entre gen e gent
Calculando distância entre ge e gent
Calculando distância entre g e gent
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre ge e gen
Calculando distância entre ge e ge
Calculando distância entre gen e gen
Distancia 1
Bem melhor que o anterior. Mas infelizmente para quem achava que ia ter esta diversão toda com algoritmos, a triste notícia é que existem excelentes implementações em boas bibliotecas gratuitas, como a implementação de alguns algoritmos fonéticos na Apache Commons Codec , e o Levenshtein no Apache Commons Lang . Com certeza serão implementações bem melhores que as minhas... Mas para um código de brinquedo, já está de bom tamanho!
