node.js - Encontrar el texto más similar en una lista de cadenas

Primero que nada, quiero reconocer que este es quizás un problema muy sofisticado; sin embargo, no he podido encontrar una respuesta definitiva en línea, por lo que estoy buscando sugerencias.

Supongamos que quiero recopilar una lista que contenga más de cien mil cadenas, los valores de estas cadenas son oraciones que un usuario ha escrito. Los valores se agregan a la lista tan pronto como un usuario escribe un nuevo mensaje. Por ejemplo:

["Hello world!", "Good morning, my name is John", "Good morning, everyone"]

Pero también quiero tener un tiempo de espera para cada cadena, así que si no se repiten dentro de 5 minutos, deberían ser eliminadas, así que lo cambio al siguiente formato:

[{message:"Hello world!", timeout: NodeJS.Timeout, count: 1}, {message:"Good morning, my name is John", timeout: NodeJS.Timeout, count: 1}, {message:"Good morning, everyone", timeout: NodeJS.Timeout, count: 1}]

Ahora supongamos que un usuario escribe el siguiente mensaje:

Buenos días, todos Quiero comparar esta cadena con todos los mensajes en la lista y si uno es 70% o más similar, actualizar el conteo de ese mensaje, de lo contrario insertarlo como un nuevo mensaje. Para este mensaje, por ejemplo, la aplicación debería actualizar el conteo de Buenos días, todos para que sea igual a 2.

Dado que los usuarios pueden escribir muchos mensajes en un corto período de tiempo, el algoritmo también debe soportar inserción rápida, búsqueda y eliminación después del tiempo de espera.

¿Cuál es la mejor manera de implementar esto? ¿O hay alguna biblioteca que me pueda ayudar con esto?

NOTA: Las cadenas no necesitan estar en un arreglo, cualquier estructura de datos funcionaría.

El propósito principal de este algoritmo es detectar mensajes similares cuando el conteo alcanza un valor predefinido. Por ejemplo advertencia: Más de 5 usuarios escribieron mensajes similares a "Hola a todos" en 5 minutos

He mirado los B-Trees, Nearest Neighbor, etc., pero no puedo averiguar cuál sería la mejor solución.

Actualización: Planeo usar la distancia de Levenshtein para la similitud de cadenas, sin embargo, el problema principal es cómo aplicar eso a una lista de cadenas de la manera más eficiente en cuanto al tiempo, sin tener que verificar cada cadena cada vez que se agrega un nuevo mensaje.

Respuesta #1

distancia de Levenshtein

A diferencia de la otra respuesta, creo que la distancia de Levenshtein es perfectamente capaz de manejar errores ortográficos. De hecho, Levenshtein y LevXenshtein solo tienen una distancia de Levenshtein de 1, y por lo tanto se puede concluir que probablemente sean el mismo mensaje.

Sin embargo, si quieres usar esta distancia, tendrás que calcular la distancia entre el nuevo mensaje y cada mensaje almacenado, cada vez que llegue un nuevo mensaje. Probablemente no haya manera de evitar esto.

Desafortunadamente, no hay un preprocesamiento realmente útil que puedas hacer para esto.

Otras posibilidades

Si puedes encontrar una manera de mapear cada mensaje a un vector de tamaño fijo, puedes usar esencialmente cualquier técnica de búsqueda del vecino más cercano. Sugiero hacerlo.

Esto nos deja con dos problemas por resolver. Generar el vector de longitud fija y hacer la búsqueda.

Representación vectorial de tamaño fijo

Hay múltiples formas de hacer esto, todas con su propio conjunto de desventajas. Mencionaré específicamente dos, pero dependerá de tu arquitectura y tus datos cuál método es mejor para ti.

Primero, podrías seguir el camino del aprendizaje automático. Podrías asignar cada palabra a un vector preentrenado con fastText, promediar las palabras en el mensaje y usar eso como tu vector. Las desventajas de este método son que ignorará el orden de las palabras y funcionará menos si las palabras usadas tienden a ser muy informales. Si tus mensajes tienen su propia cultura (como por ejemplo el chat de Twitch), tendrías que reentrenar estos vectores en lugar de usar los preentrenados.

Alternativamente, podrías usar la estructura del texto directamente y hacer un vector de ocurrencias de bigramas. Es decir, anota con qué frecuencia ocurre cada combinación de 2 caracteres en un mensaje. Esto es bastante robusto, pero tiene el inconveniente de que los vectores se volverán relativamente grandes.

De todos modos, estas son solo dos opciones, y es imposible saber qué método es ideal para ti. A menos que, por supuesto, alguien tenga una idea brillante.

Búsqueda del vecino más cercano

Dado que tenemos vectores de longitud fija, ahora podemos realizar la búsqueda del vecino más cercano. Como probablemente habrás notado, una vez más hay muchos métodos diferentes para esto, todos con sus propios inconvenientes. Agotador, lo sé.

Elegiré discutir tres categorías.

Búsqueda aproximada: Este método puede parecer un poco tonto, pero podría ser lo que quieres. Específicamente, el hashing sensible a la localidad es esencialmente solo crear alguna función de hashing donde los vectores "similares" probablemente terminen en el mismo cubo. Luego podrías hacer lo que quieras, como Levenshtein, con todos los demás miembros del cubo, porque no debería haber demasiados de ellos. La ventaja de tal algoritmo aproximado es que puede ser rápido, y con un hashing inteligente ni siquiera necesitas vectores de longitud fija. Un inconveniente, por supuesto, es que no se garantiza que funcione.
Búsqueda exacta: También podemos optar por resolver en su lugar el problema de vecinos cercanos de radio fijo. Es decir, encontrar los puntos dentro de cierta distancia del punto objetivo. Podrías hacer esto mapeando vectores a enteros (si es que no lo están ya) y simplemente revisando cada punto de la red dentro de la distancia que deseas buscar. La principal desventaja aquí es que el tiempo de búsqueda crece muy rápido, no con el número de puntos, sino con el número de dimensiones del vector. Este método requeriría vectores pequeños.
Estructuras de datos sofisticadas: Esto me parece lo más probable que sea la solución correcta. Desafortunadamente, tienes muchos árboles de letras. Mencionas los B-trees, pero también están los R-trees, R+-Trees, R*-Trees, X-Trees, y eso es solo los descendientes directos del R-tree. Con el riesgo de perder los árboles por el bosque, sugeriría echar un vistazo al k-d tree. Puede hacer búsqueda del vecino más cercano en tiempo logarítmico, así como inserción y eliminación.

Respuesta #2

Quieres convertir todas las palabras a su valor Soundex.

Entonces necesitas una base de datos para los valores soundex que clasifique la importancia de la palabra en la oración, por ejemplo, the probablemente debería obtener 0. Cuanta más información lleva la palabra, mayor es su valor.

Luego ordena las palabras en la oración en una lista de enteros.

Usa la lista de enteros como la clave para encontrar oraciones similares.

Dado que la clave es una lista de enteros, un árbol Rose debería funcionar como estructura de datos.

Mientras que algunos pueden sugerir medir usando algo como la distancia de Levenshtein que presupone que las oraciones no tienen errores ortográficos o similares. Necesitas algo que sea lo suficientemente flexible para manejar errores humanos.