سلاسل موجودة في كل مكان وغامضة. عندما يتم تأسيس قناة اتصال، يمكن للضجيج لا مفر منه وسوء الفهم إدخال أخطاء في نقل البيانات النصية.
في نظام المؤسسات، وهناك العديد من الاماكن حيث هذا النوع من الأخطاء يمكن أن تحدث. أسماء العملاء والعناوين وأسماء الشركات، وغيرها. قد يكون هذا النوع من الخطأ جعله غير عملي للاستعلام عن السجل. تخيل الحياة من المحزن لنا الممثل الشهير أرنولد عمل أفلام شوارزنيجر، كم مرة كان لتوضيح اسمه للمشغل؟
لحل هذه المشكلة، تم إنشاء بعض خوارزميات للبحث عن كلمات أقرب معا، وفيما بينها هي خوارزميات فظي. خوارزمية تستخدم قواعد لفظي لتحويل السلاسل إلى الفونيمات، في محاولة لتوحيدها مع مماثلة السبر الكلمات. أمثلة على خوارزميات:
لكن جميع هذه الخوارزميات تعاني من نفس المشاكل. مكتوبة خصيصا لقواعد لغة معينة، ويكون معظم تطبيقات اللغة الانجليزية كلغة هدف. هذه ليست مشكلة إذا كان النظام للمستخدمين ناطقة باللغة الإنجليزية، ولا ترغب في جعل التطبيقات في مختلف اللغات ... لأن العولمة على نحو متزايد هذا العالم، وأجد من الصعب جدا أن يكون هذا هو الحال ...
ولكن هناك حلول أخرى؟ أخبار جيدة! تبحث عن بدائل، واعتقدت من الكلمات للبحث خوارزميات تقريبية بعد تحرير الفئة، خصوصا بعد Levenshtein الخوارزمية . أكثر قوة وموثوق بها، ويمكن استخدامها من قبل أي مبرمج في أي لغة دون تغيير. وحتى مع وجود ميزة صغيرة، لأنه لا بإرجاع استجابة منطقية، قائلة انها كانت ناجحة أم لا في البحث، ولكن الرقم الذي يروي كيف مماثلة هي عبارة عن كلمتين، مما يجعل من الممكن لفرز مجموعة من المرشحين لله طلبت مسافة واحدة من الأرض. وهذا يمكن أن ميزة صغيرة يكون الفرق بين صفحات وصفحات من نتائج بدون قيمة، أو قائمة مرتبة مع معظم النتائج ذات الصلة أولا.
الخوارزمية من مسافة Levenshtein، والذي يدعى بعد خالقه، والروسي فلاديمير Levenshtein ، بحساب تكلفة تحويل كلمة واحدة إلى آخر، على افتراض بعض العمليات مثل إدراج أو إزالة أو استبدال حرف. ويمكن وصفها على النحو التالي:
أن تكون نفسك وخيوط SJ من الحروف ط، ي صحيحة بحيث 0 <= ط <= الحجم (النفس) و 0 <= ي <= حجم (ي). هو د (BS، SJ) وظيفة تقوم بحساب المسافة بينه وبين تحرير SJ.
وطول (سي) يساوي 0، ثم د (BS، SJ) = طول (SJ). على العكس ينطبق على SJ.
إذا كنت وSJ ليست السلاسل الفارغة، ومن ثم يمكن كتابتها كما = SI SJ si'c1 sj'c2 = و، حيث C1 هو الحرف الأخير من نفسه، و C2 هو الحرف الأخير من SJ. لذلك يذهب:
إذا C1 = C2، ثم من الواضح د (SI، SJ) = د (SI، 'سج').
إذا C1! = C2، ثم د (BS، SJ) = دقيقة (1 + د (BS، sj'c2)، 1 + د (si'c1، SJ ")، 1 + د (BS، SJ") ) = 1 + (الحد الأدنى د (BS، sj'c2)، د (si'c1، SJ ")، د (BS، SJ"))
السطر الأخير يستحق تفسيرا لذلك. إذا C1 يختلف C2، ثم المسافة بينها وبين تحرير SJ هو أصغر عدد من العمليات التي لا يتم إزالة نفسه C1، C2 أو SJ إزالتها، ونحن نعتقد أننا استبدال أو C1 إلى C2 (أو العكس بالعكس .)
كما ترون، وهذا يعطينا خوارزمية العودية الجميلة التي يمكن مكتوب بلغة جافا وكذلك:
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!
