¿Cómo implemento una búsqueda tipo "fonética"

Question

Actualmente estoy tratando de mejorar mi algoritmo de búsqueda.

Para una mejor comprensión, aquí está la lógica actual detrás de ella:
tenemos objetos con n palabras clave adjuntas en db. en la base de datos esto se resuelve a través de 2 tablas (Object, Keyword) donde el Keyword -table tiene un FK a Object. Cuando estoy construyendo mis campos de búsqueda, creo un valor de línea (ad: quitar diéresis, convertir a minúsculas, ...) de todas las palabras clave de un objeto. la misma rutina de conversión (NormalizeSearchPattern()) se realiza con los patrones de búsqueda. Estoy apoyando AND -búsqueda y palabras clave con una longitud mínima de 2 caracteres solamente!

La búsqueda algoritmo es actualmente una variante de fast-reverse-search (este ejemplo no está optimizado):

bool IsMatch(string source, string searchPattern) 
{ 
    // example: 
    // source: "hello world" 
    // searchPattern: "hello you freaky funky world" 
    // patterns[]: { "hello", "you", "freaky", "funky", "world" } 

    searchPattern = NormalizeSearchPattern(searchPattern); 
    var patterns = MagicMethodToSplitPatternIntoPatterns(searchPattern); 
    foreach (var pattern in patterns) 
    { 
     var success = false; 
     var patternLength = pattern.Length; 
     var firstChar = pattern[0]; 
     var secondChar = pattern[1]; 

     var lengthDifference = input.Length - patternLength; 
     while (lengthDifference >= 0) 
     { 
      if (source[lengthDifference--] != firstChar) 
      { 
       continue; 
      } 
      if (source[lengthDifference + 2] != secondChar) 
      { 
       continue; 
      } 

      var l = lengthDifference + 3; 
      var m = 2; 
      while (m < patternLength) 
      { 
       if (input[l] != pattern[m]) 
       { 
        break; 
       } 
       l++; 
       m++; 
      } 

      if (m == patternLength) 
      { 
       success = true; 
      } 
     } 
     if (!success) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

La normalización se realiza con (este ejemplo no está optimizado)

string RemoveTooShortKeywords(string keywords) 
    { 
     while (Regex.IsMatch(keywords, TooShortKeywordPattern, RegexOptions.Compiled | RegexOptions.Singleline)) 
     { 
      keywords = Regex.Replace(keywords, TooShortKeywordPattern, " ", RegexOptions.Compiled | RegexOptions.Singleline); 
     } 

     return keywords; 
    } 

    string RemoveNonAlphaDigits(string value) 
    { 
     value = value.ToLower(); 
     value = value.Replace("ä", "ae"); 
     value = value.Replace("ö", "oe"); 
     value = value.Replace("ü", "ue"); 
     value = value.Replace("ß", "ss"); 

     return Regex.Replace(value, "[^a-z 0-9]", " ", RegexOptions.Compiled | RegexOptions.Singleline); 
    } 

    string NormalizeSearchPattern(string searchPattern) 
    { 
     var resultNonAlphaDigits = RemoveNonAlphaDigits(searchPattern); 
     var resultTrimmed = RemoveTooShortKeywords(resultNonAlphaDigits); 
     return resultTrimmed; 
    } 

Así que esto es bastante sencillo, por lo tanto, es obvio que solo puedo lidiar con las variantes de source y searchPattern que he implementado en NormalizeSearchPattern() (como se mencionó anteriormente: diéresis, diferencias de mayúsculas y minúsculas, ...).

Pero, ¿cómo debería mejorar el algoritmo (o NormalizeSearchPattern()) para ser no sensible cuando se trata de:

• singular/plural
• misstyping (por ejemplo, "hauserr" < -> "Hauser. ")
• ...

Sólo para saber más sobre el diseño:
Esta aplicación se hace en C#, que almacena la búsqueda árboles y objetos en una variable estática (para consultar la base de datos solo una vez en init), el rendimiento debe ser sobresaliente (actualmente se consultan 500.000 valores de línea en menos de 300 ms).

Answer 1

Usted también puede estar interesado en una Trigram and Bigram search matching algorithm:

trigrama de búsqueda es un poderoso método de búsqueda de texto cuando la sintaxis exacta o la ortografía del objeto de destino no es precisamente conocida . Encuentra objetos que coinciden con la cantidad máxima de cadenas de tres caracteres en los términos de búsqueda introducidos, es decir, cerca de las coincidencias. Se puede especificar un umbral como punto de corte, después de lo cual ya no se considera un resultado como una coincidencia.

Answer 2

Intente buscar algo llamado levenstein distance que calcula cuántos cambios se requieren para cambiar una palabra a otra.

Pocos cambios indican palabras muy similares.

Para la coincidencia de plurales también puede usar tablas de alias si la forma plural es muy diferente de singular pero aún desea que coincidan. Supongo que Google usa alguna forma de listas de alias para sus sugerencias de preguntas alternativas.

Answer 3

Debe investigar el algoritmo Soundex. Es un algoritmo para convertir palabras en un espacio fonético, de modo que palabras que suenan de forma similar (y mal escritas) se correlacionan con los mismos valores (o similares). Hay una lista de other phonetic algorithms on wikipedia:

• Soundex, que fue desarrollado para apellidos codifican para el uso en los censos. Los códigos de Soundex son cadenas de cuatro caracteres compuestas de una letra seguidas de tres números.
  • Daitch-Mokotoff Soundex, que es un refinamiento de Soundex diseñado para apellidos con mejor coincidencia de origen eslovaco y germánico. Daitch-Mokotoff Los códigos Soundex son cadenas compuestas de de seis dígitos numéricos.
  • Kölner Phonetik que es similar a Soundex, pero más adecuado para palabras en alemán.
  • Metaphone y Double Metaphone, que es adecuado para usar con la mayoría de las palabras en inglés , no solo en los nombres. Algoritmos de metafonía son la base para muchos correctores ortográficos populares.
  • Miracode
  • Nueva York identificación del estado y el Sistema de Inteligencia (NYSIIS), que mapea los fonemas similares a la misma letra. El resultado es una cadena que puede ser pronunciada por el lector sin decodificación.
  • Match Rating Approach desarrollado por Western Airlines en 1977 - este algoritmo tiene una técnica de comparación de codificación y rango .