Smallthoughts

स्ट्रिंग्स सर्वव्यापक और अस्पष्ट हैं. जब एक संचार चैनल की स्थापना की है, एक अपरिहार्य शोर और ग़लतफ़हमियाँ मूलपाठ का डेटा के हस्तांतरण में त्रुटियों मिलवा सकता है.

एक उद्यम प्रणाली में, वहाँ कई स्थानों पर जहां त्रुटि के इस प्रकार हो सकता है. ग्राहकों के नाम, पते, दूसरों के बीच कंपनी के नाम,. त्रुटि इस प्रकार का यह एक रिकॉर्ड के लिए क्वेरी के लिए अव्यावहारिक बना सकते हैं. हमारे प्रसिद्ध अभिनेता अर्नाल्ड श्वार्जनेगर एक्शन फिल्मों के उदास जीवन, कितनी बार वह ऑपरेटर के लिए उसका नाम जादू करने के लिए किया था की कल्पना करो?

इस समस्या को हल करने के लिए, कुछ एल्गोरिदम के करीब एक साथ शब्दों के लिए खोज बनाया गया था, और उन के बीच में ध्वन्यात्मक एल्गोरिदम रहे हैं. एक एल्गोरिथ्म phonemes में तार को बदलने के लिए ध्वन्यात्मक नियम का उपयोग करता है, यह समान लग शब्दों के साथ एकजुट करने की कोशिश कर रहा है. एल्गोरिदम के उदाहरण:

• Soundex
• Soundex daitch - Mokotoff के
• Metaphone
• डबल Metaphone

लेकिन इन सभी एल्गोरिदम एक ही समस्या से पीड़ित हैं. नियम किसी विशेष भाषा के लिए विशेष रूप से लिखे गए हैं, और सबसे कार्यान्वयन लक्ष्य भाषा के रूप में अंग्रेजी है. यह एक समस्या नहीं है अगर आपके सिस्टम अंग्रेजी बोलने वाले उपयोगकर्ताओं के लिए है और आप विभिन्न भाषाओं में अनुप्रयोगों के बनाने में कोई दिलचस्पी नहीं कर रहे हैं ... क्योंकि इस दुनिया में तेजी से वैश्विक है, मैं खोजने के लिए यह बहुत कठिन मामला है ...

लेकिन वहाँ अन्य समाधान कर रहे हैं? अच्छी खबर है! विकल्प के लिए खोज रहे हैं, मैं शब्दों के बारे में सोचा एल्गोरिदम लगभग संपादित दूरी वर्ग, विशेष रूप से खोज Levenshtein दूरी एल्गोरिथ्म . अधिक मजबूत और विश्वसनीय, परिवर्तन के बिना किसी भी भाषा में किसी भी प्रोग्रामर द्वारा इस्तेमाल किया जा सकता है. और यहां तक ​​कि एक छोटे से लाभ के साथ: यह न केवल एक बूलियन प्रतिक्रिया देता है, कह रही है यह सफल या खोज में नहीं था, लेकिन एक संख्या है कि इसी तरह कैसे बताता है दो शब्द है, जो इसके लिए उम्मीदवारों के एक संग्रह को सॉर्ट करने के लिए संभव बनाता है फर्श से दूरी का अनुरोध किया. इस छोटे से लाभ पृष्ठों और परिणाम का मूल्य बिना पृष्ठों, या सबसे अधिक प्रासंगिक पहले परिणाम के साथ एक आदेश दिए सूची के बीच का अंतर हो सकता है.

Levenshtein दूरी एल्गोरिथ्म, जो इसके निर्माता, रूसी व्लादिमीर Levenshtein के नाम पर है , दूसरे में एक शब्द को बदलने, के रूप में सम्मिलित करने के लिए, हटाने या एक चरित्र की जगह कुछ संचालन संभालने की लागत की गणना. के रूप में वर्णित किया जा सकता है:

अपने आप को और मैं अक्षर का एसजे तार, जम्मू पूर्णांक ऐसा है कि 0 <= i <= आकार (स्वयं) और 0 <= j <= आकार (जे). घ (बी एस, sj) समारोह में है कि खुद को और sj के बीच संपादित दूरी की गणना करता है.

एक लंबाई (सी) 0 के बराबर है, तो (बी एस, sj) = लंबाई (एसजे). बातचीत sj के लिए रखती है.

यदि आप और एसजे खाली तार, तो सी = sj = sj'c2 si'c1 और, जहां C1 खुद के पिछले चरित्र के रूप में लिखा जा सकता है, और c2 sj के अंतिम चरित्र है. तो यह जाता है:

यदि C1 = c2, तो जाहिर है घ (सी, sj) = घ (सी, sj ').

यदि C1 =! C2, तो घ (बी एस, sj) = मिनट (1 घ (बी एस, sj'c2), 1 + घ (si'c1, एसजे "), 1 (घ बी एस ', एसजे") ) = + 1 (न्यूनतम (बी एस डी ', sj'c2), घ (si'c1, sj), (बी एस' d, एसजे "))

अंतिम पंक्ति के एक विवरण के लायक है. यदि C1 के c2 से अलग है, तो खुद को और sj के बीच दूरी संपादित करें कि आपरेशन ही C1 C2, या हटा दिया एसजे हटाने की छोटी संख्या है, हमें विश्वास है कि हम जगह या सी 2 सी 1 (या इसके ठीक विपरीत ).

जैसा कि आप देख सकते हैं, यह हमें एक खूबसूरत पुनरावर्ती एल्गोरिथ्म देता है कि जावा में के रूप में अच्छी तरह से लिखा जा सकता है:

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!