algorithm - tag - Algoritmo para autocompletar?

tags para responder

Question

Me refiero al algoritmo que se utiliza para dar sugerencias de consulta cuando un usuario escribe un término de búsqueda en Google.

Estoy interesado principalmente en cómo el algoritmo de Google es capaz de mostrar: 1. Resultados más importantes (las consultas más probables en lugar de cualquier cosa que coincida) 2. Subárbol de coincidencia 3. Partidos borrosos

Sé que podrías usar Trie o trie generalizado para encontrar coincidencias, pero no cumpliría con los requisitos anteriores ...

Preguntas similares hechas antes here

Answer 1

Creo que sería mejor construir un trie especializado, en lugar de buscar una estructura de datos completamente diferente.

Pude ver esa funcionalidad manifestada en un trie en el cual cada hoja tenía un campo que reflejaba la frecuencia de búsquedas de su palabra correspondiente.

El método de consulta de búsqueda mostraría los nodos hoja descendientes con los valores más grandes calculados a partir de la multiplicación de la distancia a cada nodo hoja descendiente por la frecuencia de búsqueda asociada con cada nodo hoja descendiente.

La estructura de datos (y, en consecuencia, el algoritmo) que usa Google es probablemente mucho más complicada, lo que podría tener en cuenta una gran cantidad de otros factores, como las frecuencias de búsqueda de su cuenta específica (y hora del día ... y del clima ... ... y la fase lunar ... y ...). Sin embargo, creo que la estructura de datos básicos puede ampliarse a cualquier tipo de preferencia de búsqueda especializada incluyendo campos adicionales para cada uno de los nodos y usando esos campos en el método de consulta de búsqueda.

Answer 2

Echa un vistazo al algoritmo de la barra Awesome de Firefox

Google Suggest es útil, porque toma en cuenta las millones de consultas populares + consultas pasadas relacionadas.

Sin embargo, no tiene un buen algoritmo / UI de finalización:

1. No hace subcadenas
2. Parece un algoritmo de prefijo de límite de palabra relativamente simple.
   Por ejemplo: Pruebe tomcat tut -> sugiera correctamente "tutorial de tomcat". Ahora prueba tomcat rial -> sin sugerencias) -:
3. No es compatible con "¿quisiste decir?" - como en los resultados de búsqueda de Google.

Answer 3

El algoritmo exacto de Google se desconoce, pero se dice que funciona mediante el análisis estadístico de la entrada de los usuarios. Un enfoque no adecuado para la mayoría de los casos. Más comúnmente la finalización automática se implementa mediante uno de los siguientes:

• Árboles Al indexar el texto que se puede buscar en una estructura en árbol (árbol de prefijos, árbol de sufijos, dawg, etc.) uno puede ejecutar búsquedas muy rápidas a expensas del almacenamiento de la memoria. El recorrido del árbol se puede adaptar para una coincidencia aproximada.
• Partición del patrón . Al dividir el texto en tokens (ngrams), se pueden ejecutar búsquedas de ocurrencias de patrones usando un simple esquema de hash.
• Filtrando Encuentre un conjunto de posibles coincidencias y luego aplique un algoritmo secuencial para verificar cada candidato.

Echa un vistazo a completely , una biblioteca de autocompletado de Java que implementa algunos de los últimos conceptos.

Answer 4

Hay herramientas como la distancia soundex y levenshtein que se pueden usar para encontrar coincidencias difusas que están dentro de un cierto rango.

Soundex encuentra palabras que suenan similares y distancia levenshtein encuentra palabras que están dentro de una cierta distancia de edición de otra palabra.

Answer 5

Para (heh) asombrosos algoritmos de coincidencia de cadenas difusas / parciales, echa un vistazo a Damn Cool Algorithms:

• http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
• http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata

Estos no reemplazan los intentos, sino que evitan las búsquedas de fuerza bruta en los intentos, lo cual es una gran victoria. A continuación, probablemente desee una forma de enlazar el tamaño del trie:

• mantener un trie de las palabras N recientes / superiores usadas globalmente;
• para cada usuario, mantenga un trie de palabras N recientes / superiores para ese usuario.

Finalmente, desea evitar búsquedas siempre que sea posible ...

• resultados de búsqueda de caché: si el usuario hace clic en los resultados de búsqueda, puede servirlos rápidamente y luego buscar de forma asíncrona la búsqueda completa parcial / difusa.
• resultados de búsqueda precomputada: si el usuario ha escrito "appl", es probable que continúe con "apple", "apply".
• datos de captación previa: por ejemplo, una aplicación web puede enviar un conjunto de resultados más pequeño al navegador, lo suficientemente pequeño como para hacer viable la búsqueda de fuerza bruta en JS.

Answer 6

Para las subcadenas y las coincidencias borrosas, el algoritmo de distancia de Levenshtein me ha funcionado bastante bien. Aunque admitiré que no parece ser tan perfecto como las implementaciones industriales de autocompletar / sugerir. Tanto el Intellisense de Google como el de Microsoft hacen un mejor trabajo, creo que debido a que han refinado este algoritmo básico para evaluar el tipo de operaciones de edición que se necesitan para hacer coincidir las diferentes cadenas. Por ejemplo, la transposición de dos caracteres probablemente solo cuente como 1 operación, no 2 (una inserción y eliminación).

Pero aun así, creo que esto es lo suficientemente cercano. Aquí está su implementación en C # ...

// This is the traditional Levenshtein Distance algorithem, though I''ve tweaked it to make
// it more like Google''s autocomplete/suggest.  It returns the number of operations 
// (insert/delete/substitute) required to change one string into another, with the 
// expectation that userTyped is only a partial version of fullEntry.
// Gives us a measurement of how similar the two strings are.
public static int EditDistance(string userTyped, string fullEntry)
{
    if (userTyped.Length == 0) // all entries are assumed to be fully legit possibilities 
        return 0; // at this point, because the user hasn''t typed anything.

    var inx = fullEntry.IndexOf(userTyped[0]);
    if (inx < 0) // If the 1st character doesn''t exist anywhere in the entry, it''s not
        return Int32.MaxValue; // a possible match.

    var lastInx = inx;
    var lastMatchCount = 0;
TryAgain:
    // Is there a better starting point?
    var len = fullEntry.Length - inx;
    var matchCount = 1;
    var k = 1;
    for (; k < len; k++)
    {
        if (k == userTyped.Length || userTyped[k] != fullEntry[k + inx])
        {
            if (matchCount > lastMatchCount)
            {
                lastMatchCount = matchCount;
                lastInx = inx;
            }
            inx = fullEntry.IndexOf(userTyped[0], inx + 1);
            matchCount = 0;
            if (inx > 0)
                goto TryAgain;
            else
                break;
        }
        else
            matchCount++;
    }
    if (k == len && matchCount > lastMatchCount)
        lastInx = inx;

    if (lastInx > 0)
        fullEntry = fullEntry.Substring(lastInx); // Jump to 1st character match, ignoring previous values 

    // The start of the Levenshtein Distance algorithem.
    var m = userTyped.Length;
    var n = Math.Min(m, fullEntry.Length);

    int[,] d = new int[m + 1, n + 1]; // "distance" - meaning number of operations.

    for (var i = 0; i <= m; i++)
        d[i, 0] = i; // the distance of any first string to an empty second string
    for (var j = 0; j <= n; j++)
        d[0, j] = j; // the distance of any second string to an empty first string

    for (var j = 1; j <= n; j++)
        for (var i = 1; i <= m; i++)
            if (userTyped[i - 1] == fullEntry[j - 1])
                d[i, j] = d[i - 1, j - 1];       // no operation required
            else
                d[i, j] = Math.Min
                           (
                             d[i - 1, j] + 1,  // a deletion
                             Math.Min(
                             d[i, j - 1] + 1,  // an insertion
                             d[i - 1, j - 1] + 1 // a substitution
                             )
                           );

    return d[m, n];
}

Answer 7

Si está buscando un diseño general para el problema, intente leer el contenido en https://www.interviewbit.com/problems/search-typeahead/ .

Comienzan construyendo autocompletar a través de un enfoque ingenuo de usar un trie y luego construir sobre él. También explican técnicas de optimización como muestreo y actualizaciones fuera de línea para atender casos de uso específicos.

Para mantener la solución escalable, deberá fragmentar sus datos de forma inteligente.

Answer 8

Solo me gustaría decir ... Una buena solución a este problema va a incorporar más que un árbol de búsqueda ternaria. Ngrams y Shingles (Frases) son necesarios. Los errores de límite de palabra también deben ser detectados. "hell o" debería ser "hola" ... y "whitesocks" debería ser "calcetines blancos": estos son pasos previos al procesamiento. Si no preprocesas los datos correctamente, no obtendrás resultados de búsqueda valiosos. Los árboles de búsqueda ternaria son un componente útil para descubrir qué es una palabra, y también para implementar la adivinación de palabras relacionadas cuando una palabra escrita no es una palabra válida en el índice.

El algoritmo de google realiza sugerencia y corrección de frase. El algoritmo de Google también tiene algún concepto de contexto ... si la primera palabra que buscas está relacionada con el clima y las combinas "weatherforcst" vs "monsoonfrcst" versus "deskfrcst" - mi conjetura es que las clasificaciones detrás de las escenas se están cambiando en el sugerencia basada en la primera palabra encontrada - el pronóstico y el clima son palabras relacionadas, por lo tanto, pronostica obtener un alto rango en la suposición de Did-You-Mean.

parciales de palabras (ngramos), términos de frase (culebrilla), proximidad de palabras (índice de clustering de palabras), árbol de búsqueda ternario (búsqueda de palabras).