para - Mejorando el resultado de búsqueda usando la distancia de Levenshtein en Java

algoritmos para comparar textos

Question

He seguido el código de Java que funciona para buscar una palabra en una lista de palabras y funciona perfectamente y como se esperaba:

public class Levenshtein {
    private int[][] wordMartix;

    public Set similarExists(String searchWord) {

        int maxDistance = searchWord.length();
        int curDistance;
        int sumCurMax;
        String checkWord;

        // preventing double words on returning list
        Set<String> fuzzyWordList = new HashSet<>();

        for (Object wordList : Searcher.wordList) {
            checkWord = String.valueOf(wordList);
            curDistance = calculateDistance(searchWord, checkWord);
            sumCurMax = maxDistance + curDistance;
            if (sumCurMax == checkWord.length()) {
                fuzzyWordList.add(checkWord);
            }
        }
        return fuzzyWordList;
    }

    public int calculateDistance(String inputWord, String checkWord) {
        wordMartix = new int[inputWord.length() + 1][checkWord.length() + 1];

        for (int i = 0; i <= inputWord.length(); i++) {
            wordMartix[i][0] = i;
        }

        for (int j = 0; j <= checkWord.length(); j++) {
            wordMartix[0][j] = j;
        }

        for (int i = 1; i < wordMartix.length; i++) {
            for (int j = 1; j < wordMartix[i].length; j++) {
                if (inputWord.charAt(i - 1) == checkWord.charAt(j - 1)) {
                    wordMartix[i][j] = wordMartix[i - 1][j - 1];
                } else {
                    int minimum = Integer.MAX_VALUE;
                    if ((wordMartix[i - 1][j]) + 1 < minimum) {
                        minimum = (wordMartix[i - 1][j]) + 1;
                    }

                    if ((wordMartix[i][j - 1]) + 1 < minimum) {
                        minimum = (wordMartix[i][j - 1]) + 1;
                    }

                    if ((wordMartix[i - 1][j - 1]) + 1 < minimum) {
                        minimum = (wordMartix[i - 1][j - 1]) + 1;
                    }

                    wordMartix[i][j] = minimum;
                }
            }
        }

        return wordMartix[inputWord.length()][checkWord.length()];
    }

}

Ahora cuando busco una palabra como job , devuelve una lista:

Salida

joborienterede
jobannoncer
jobfunktioner
perjacobsen
jakobsen
jobprofiler
jacob
jobtitler
jobbet
jobdatabaserne
jobfunktion
jakob
jobs
studenterjobber
johannesburg
jobmuligheder
jobannoncerne
jobbaser
job
joberfaringer

Como puede ver, la salida tiene muchas palabras relacionadas, pero también tiene palabras no relacionadas como jakob , jacob , etc., lo cual es correcto con respecto a la fórmula de Levenshtein, pero me gustaría construir más y escribir un método que pueda ajustar mi buscar para poder obtener palabras más relevantes y relacionadas.

He trabajado algunas horas en él y he perdido la visión de la creatividad.

Mi pregunta: ¿es posible afinar el método existente para devolver palabras relevantes / relacionadas O debería tomar otro enfoque O ??? en todos los casos SÍ o NO, me gustó si puedo obtener insumos e inspiración para mejorar los resultados de búsqueda?

ACTUALIZAR

Después de hacer esta pregunta hace mucho tiempo, realmente no he encontrado una solución y vuelvo a ella porque es hora de que necesite una respuesta útil, está bien proporcionar la respuesta con muestras de código JAVA, pero lo más importante es un detallado respuesta con una descripción de los métodos y enfoques disponibles utilizados para indexar los mejores y más relevantes resultados de búsqueda e ignorando palabras relevantes . Sé que este es un área abierta e interminable, pero necesito tener algo de inspiración para comenzar en algún lado.

Nota: La respuesta más antigua en este momento se basa en una de las entradas de comentario y no es útil (inútil), simplemente ordenando la distancia, eso no significa obtener mejores resultados de búsqueda / calidad.

Así que hice la clasificación por distancia y los resultados fueron así:

job
jobs
jacob
jakob
jobbet
jakobsen
jobbaser
jobtitler
jobannoncer
jobfunktion
jobprofiler
perjacobsen
johannesburg
jobannoncerne
joberfaringer
jobfunktioner
jobmuligheder
jobdatabaserne
joborienterede
studenterjobber

así que la palabra jobbaser es relevante y jacob / jakob no es relevante, pero la distancia para jobbaser es más grande que jacob / jakob. Entonces eso realmente no ayudó.

Comentarios generales con respecto a las respuestas

• @SergioMontoro, resuelve casi el problema.
• @uSeemSurprised, resuelve el problema pero necesita una manipulación continua.
• El concepto de @Gene es excelente, pero se está retransmitiendo en una URL externa.

Gracias personalmente me gustaría agradecer a todos ustedes que contribuyeron a esta pregunta, tengo buenas respuestas y comentarios útiles.

Gracias especiales a las respuestas de @SergioMontoro, @uSeemSurprised y @Gene, esas son respuestas diferentes pero válidas y útiles.

@ D.Kovács señala una solución interesante.

Ojalá pudiera dar generosidad a todas esas respuestas. Eligió una respuesta y le dio recompensa, eso no significa que las otras respuestas no sean válidas, pero eso solo significa que la respuesta particular que elegí fue útil para mí.

Answer 1

Esta es realmente una pregunta abierta, pero sugeriría un enfoque alternativo que utiliza, por ejemplo, el algoritmo de Smith-Waterman como se describe en este SO .

Otra solución (más liviana) sería usar otras medidas de distancia / similitud de NLP (p. Ej., Similitud de coseno o distancia de Damerau-Levenshtein ).

Answer 2

Probé la sugerencia de los comentarios sobre clasificar las coincidencias por la distancia devuelta por Levenshtein algo, y parece que produce mejores resultados.

(Como no pude encontrar cómo no pude encontrar la clase Searcher de su código, me tomé la libertad de usar una fuente diferente de lista de palabras, implementación de Levenshtein e idioma).

Usando la lista de palabras proporcionada en Ubuntu, y la implementación de algo de Levenshtein desde - https://github.com/ztane/python-Levenshtein , creé un pequeño script que pide una palabra e imprime todas las palabras más cercanas y la distancia como tupla.

Código - https://gist.github.com/atdaemon/9f59ad886c35024bdd28

from Levenshtein import distance
import os

def read_dict() :
    with open(''/usr/share/dict/words'',''r'') as f : 
        for line in f :
            yield str(line).strip()

inp = str(raw_input(''Enter a word : ''))

wordlist = read_dict()
matches = []
for word in wordlist :
    dist = distance(inp,word)
    if dist < 3 :
        matches.append((dist,word))
print os.linesep.join(map(str,sorted(matches)))

Muestra de salida -

Enter a word : job
(0, ''job'')
(1, ''Bob'')
(1, ''Job'')
(1, ''Rob'')
(1, ''bob'')
(1, ''cob'')
(1, ''fob'')
(1, ''gob'')
(1, ''hob'')
(1, ''jab'')
(1, ''jib'')
(1, ''jobs'')
(1, ''jog'')
(1, ''jot'')
(1, ''joy'')
(1, ''lob'')
(1, ''mob'')
(1, ''rob'')
(1, ''sob'')
...

Enter a word : checker
(0, ''checker'')
(1, ''checked'')
(1, ''checkers'')
(2, ''Becker'')
(2, ''Decker'')
(2, ''cheaper'')
(2, ''cheater'')
(2, ''check'')
(2, "check''s")
(2, "checker''s")
(2, ''checkered'')
(2, ''checks'')
(2, ''checkup'')
(2, ''cheeked'')
(2, ''cheekier'')
(2, ''cheer'')
(2, ''chewer'')
(2, ''chewier'')
(2, ''chicer'')
(2, ''chicken'')
(2, ''chocked'')
(2, ''choker'')
(2, ''chucked'')
(2, ''cracker'')
(2, ''hacker'')
(2, ''heckler'')
(2, ''shocker'')
(2, ''thicker'')
(2, ''wrecker'')

Answer 3

Puede modificar la distancia de Levenshtein ajustando la puntuación cuando coincidan los caracteres consecutivos.

Siempre que haya caracteres consecutivos que coincidan, la puntuación puede reducirse, haciendo que la búsqueda sea más relevante.

Ejemplo: Digamos que el factor por el cual queremos reducir el puntaje es 10, entonces si en una palabra encontramos la subcadena "trabajo" podemos reducir el puntaje en 10 cuando encontramos "j" furthur reducirlo en (10 + 20) cuando encontramos la cadena "jo" y finalmente reducimos la puntuación en (10 + 20 + 30) cuando encontramos "trabajo".

He escrito un código de C ++ a continuación:

#include <bits/stdc++.h>

#define INF -10000000
#define FACTOR 10

using namespace std;

double memo[100][100][100];

double Levenshtein(string inputWord, string checkWord, int i, int j, int count){
    if(i == inputWord.length() && j == checkWord.length()) return 0;    
    if(i == inputWord.length()) return checkWord.length() - j;
    if(j == checkWord.length()) return inputWord.length() - i;
    if(memo[i][j][count] != INF) return memo[i][j][count];

    double ans1 = 0, ans2 = 0, ans3 = 0, ans = 0;
    if(inputWord[i] == checkWord[j]){
        ans1 = Levenshtein(inputWord, checkWord, i+1, j+1, count+1) - (FACTOR*(count+1));
        ans2 = Levenshtein(inputWord, checkWord, i+1, j, 0) + 1;
        ans3 = Levenshtein(inputWord, checkWord, i, j+1, 0) + 1;
        ans = min(ans1, min(ans2, ans3));
    }else{
        ans1 = Levenshtein(inputWord, checkWord, i+1, j, 0) + 1;
        ans2 = Levenshtein(inputWord, checkWord, i, j+1, 0) + 1;
        ans = min(ans1, ans2);
    }
    return memo[i][j][count] = ans;
}

int main(void) {
    // your code goes here
    string word = "job";
    string wordList[40];
    vector< pair <double, string> > ans;
    for(int i = 0;i < 40;i++){
        cin >> wordList[i];
        for(int j = 0;j < 100;j++) for(int k = 0;k < 100;k++){
            for(int m = 0;m < 100;m++) memo[j][k][m] = INF;
        }
        ans.push_back( make_pair(Levenshtein(word, wordList[i], 
            0, 0, 0), wordList[i]) );
    }
    sort(ans.begin(), ans.end());
    for(int i = 0;i < ans.size();i++){
        cout << ans[i].second << " " << ans[i].first << endl;
    }
    return 0;
}

Enlace a la demostración: http://ideone.com/4UtCX3

Aquí el FACTOR se toma como 10, puede experimentar con otras palabras y elegir el valor apropiado.

También tenga en cuenta que la complejidad de la Distancia Levenshtein anterior también ha aumentado, ahora es O(n^3) lugar de O(n^2) ya que ahora también estamos siguiendo el contador que cuenta cuántos caracteres consecutivos hemos encontrado .

Puede seguir jugando con el puntaje aumentando gradualmente después de encontrar una subcadena consecutiva y luego una discrepancia, en lugar de la forma actual en la que tenemos un puntaje fijo de 1 que se agrega al puntaje general.

También en la solución anterior puede eliminar las cadenas que tienen puntaje> = 0, ya que no son para nada relevistas, también puede elegir algún otro umbral para que tenga una búsqueda más precisa.

Answer 4

Sin entender el significado de las palabras como sugiere @DrYap, la siguiente unidad lógica para comparar dos palabras (si no está buscando errores ortográficos) son las sílabas. Es muy fácil modificar Levenshtein para comparar sílabas en lugar de caracteres. La parte difícil es dividir las palabras en sílabas. Hay una implementación Java TeXHyphenator-J que se puede usar para dividir las palabras. En base a esta biblioteca de separación por sílabas, aquí hay una versión modificada de la función de Levenshtein escrita por Michael Gilleland y Chas Emerick . Más sobre la detección de sílabas here y here . Por supuesto, querrás evitar la comparación de sílabas de dos palabras de una sola sílaba, probablemente manejando este caso con Levenshtein estándar.

import net.davidashen.text.Hyphenator;

public class WordDistance {

    public static void main(String args[]) throws Exception {
        Hyphenator h = new Hyphenator();
        h.loadTable(WordDistance.class.getResourceAsStream("hyphen.tex"));
        getSyllableLevenshteinDistance(h, args[0], args[1]);
    }

    /**
     * <p>
     * Calculate Syllable Levenshtein distance between two words </p>
     * The Syllable Levenshtein distance is defined as the minimal number of
     * case-insensitive syllables you have to replace, insert or delete to transform word1 into word2.
     * @return int
     * @throws IllegalArgumentException if either str1 or str2 is <b>null</b>
     */
    public static int getSyllableLevenshteinDistance(Hyphenator h, String s, String t) {
        if (s == null || t == null)
            throw new NullPointerException("Strings must not be null");

        final String hyphen = Character.toString((char) 173);
        final String[] ss = h.hyphenate(s).split(hyphen);
        final String[] st = h.hyphenate(t).split(hyphen);

        final int n = ss.length;
        final int m = st.length;

        if (n == 0)
            return m;
        else if (m == 0)
            return n;

        int p[] = new int[n + 1]; // ''previous'' cost array, horizontally
        int d[] = new int[n + 1]; // cost array, horizontally

        for (int i = 0; i <= n; i++)
            p[i] = i;

        for (int j = 1; j <= m; j++) {
            d[0] = j;
            for (int i = 1; i <= n; i++) {
                int cost = ss[i - 1].equalsIgnoreCase(st[j - 1]) ? 0 : 1;
                // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
                d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
            }
            // copy current distance counts to ''previous row'' distance counts
            int[] _d = p;
            p = d;
            d = _d;
        }

        // our last action in the above loop was to switch d and p, so p now actually has the most recent cost counts
        return p[n];
    }

}

Answer 5

Ya que me preguntó, le mostraré cómo puede hacer swoogle.umbc.edu/SimService/index.html en este tipo de cosas. No estoy seguro de que sea lo que realmente quieres:

import static java.lang.String.format;
import static java.util.Comparator.comparingDouble;
import static java.util.stream.Collectors.toMap;
import static java.util.function.Function.identity;

import java.util.Map.Entry;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.HttpURLConnection;
import java.net.URL;
import java.util.Arrays;
import java.util.regex.Pattern;

public class SemanticSimilarity {
  private static final String GET_URL_FORMAT
      = "http://swoogle.umbc.edu/SimService/GetSimilarity?"
          + "operation=api&phrase1=%s&phrase2=%s";
  private static final Pattern VALID_WORD_PATTERN = Pattern.compile("//w+");
  private static final String[] DICT = {
    "cat",
    "building",
    "girl",
    "ranch",
    "drawing",
    "wool",
    "gear",
    "question",
    "information",
    "tank" 
  };

  public static String httpGetLine(String urlToRead) throws IOException {
    URL url = new URL(urlToRead);
    HttpURLConnection conn = (HttpURLConnection) url.openConnection();
    conn.setRequestMethod("GET");
    try (BufferedReader reader = new BufferedReader(
        new InputStreamReader(conn.getInputStream()))) {
      return reader.readLine();
    }
  }

  public static double getSimilarity(String a, String b) {
    if (!VALID_WORD_PATTERN.matcher(a).matches()
        || !VALID_WORD_PATTERN.matcher(b).matches()) {
      throw new RuntimeException("Bad word");
    }
    try {
      return Double.parseDouble(httpGetLine(format(GET_URL_FORMAT, a, b)));
    } catch (IOException | NumberFormatException ex) {
      return -1.0;
    }
  }

  public static void test(String target) throws IOException {
    System.out.println("Target: " + target);
    Arrays.stream(DICT)
        .collect(toMap(identity(), word -> getSimilarity(target, word)))
        .entrySet().stream()
        .sorted((a, b) -> Double.compare(b.getValue(), a.getValue()))
        .forEach(System.out::println);
    System.out.println();
  }

  public static void main(String[] args) throws Exception {
    test("sheep");
    test("vehicle");
    test("house");
    test("data");
    test("girlfriend");
  }
}

Los resultados son fascinantes:

Target: sheep
ranch=0.38563728
cat=0.37816614
wool=0.36558008
question=0.047607
girl=0.0388761
information=0.027191084
drawing=0.0039623436
tank=0.0
building=0.0
gear=0.0

Target: vehicle
tank=0.65860236
gear=0.2673374
building=0.20197356
cat=0.06057514
information=0.041832563
ranch=0.017701812
question=0.017145569
girl=0.010708235
wool=0.0
drawing=0.0

Target: house
building=1.0
ranch=0.104496084
tank=0.103863
wool=0.059761923
girl=0.056549154
drawing=0.04310725
cat=0.0418914
gear=0.026439993
information=0.020329408
question=0.0012588014

Target: data
information=0.9924584
question=0.03476312
gear=0.029112043
wool=0.019744944
tank=0.014537057
drawing=0.013742204
ranch=0.0
cat=0.0
girl=0.0
building=0.0

Target: girlfriend
girl=0.70060706
ranch=0.11062875
cat=0.09766617
gear=0.04835723
information=0.02449007
wool=0.0
question=0.0
drawing=0.0
tank=0.0
building=0.0