Determinar qué tan similar es una cadena dada a una colección de cadenas

10

No estoy seguro si esta pregunta pertenece aquí y me disculpo si no. Lo que estoy buscando hacer es desarrollar una forma programática en la que pueda determinar probabilísticamente si una cadena dada "pertenece" en una bolsa de cadenas. Por ejemplo, si tengo una bolsa de 10,000 nombres de ciudades de EE. UU. Y luego tengo la cadena "Filadelfia", me gustaría una medida cuantitativa de la probabilidad de que 'Filadelfia' sea un nombre de ciudad de EE. UU. Basado en los nombres de ciudades de EE. UU. Si bien sé que no podré separar nombres de ciudades reales de nombres de ciudades falsas en este contexto, al menos esperaría tener cadenas como "123.75" y "El zorro rojo rápido saltó sobre los perros marrones perezosos" excluido dado Algún umbral.

Para comenzar, miré Levenshtein Distance y examiné un poco cómo se ha aplicado a problemas al menos algo similares a los que estoy tratando de resolver. Una aplicación interesante que encontré fue la detección de plagio, con un artículo que describe cómo se utilizó la distancia de Levenshtein con un algoritmo modificado de Smith-Waterman para calificar los documentos según la probabilidad de que fueran una versión plagarizada de un documento base dado. Mi pregunta es si alguien podría señalarme en la dirección correcta con otros algoritmos o metodologías establecidas que podrían ayudarme. Tengo la sensación de que esto puede ser un problema que alguien en el pasado ha intentado resolver, pero hasta ahora mi Google-fu me ha fallado.

algorithms reference-request string-metrics Andrés
fuente
Si tiene ejemplos positivos y negativos disponibles, entonces podría intentar entrenar a un clasificador. Para las características, para comenzar, trataría de obtener algunas estadísticas simples como las sugeridas por Yuval Filmus.
Nick
Tenga en cuenta esta pregunta relacionada .
Raphael
Los nombres de ciudades parecen ser un mal ejemplo; están por todas partes, especialmente en los Estados Unidos. Aquí, la búsqueda en la tabla parece ser la forma más efectiva. ¿Tu problema es más general?
Raphael

Respuestas:

5

Algunas mejores estadísticas para pensar son la longitud de palabras y el análisis de gramas. Para la longitud de las palabras, puede recopilar estadísticas de la distribución de la longitud de las palabras de los nombres de ciudades y compararlas con la longitud de lo que obtiene. El análisis de gramas analiza la distribución de secuencias de letras en el texto de muestra (digamos ). Ambos enfoques se pueden combinar.nnnn=2

Dada la heurística, puede usar la probabilidad de obtener una puntuación que (con suerte) sería más alta para sus datos de muestra que para otro texto. Para determinar un umbral razonable, puede realizar una validación cruzada. Elija un conjunto de frases de muestra que no sean nombres de ciudades. Divida los nombres de las ciudades en dos partes, una parte grande (digamos 80%) y una pequeña (digamos 20%). Entrene a su modelo en la parte grande (es decir, recopile estadísticas en la parte grande) y luego evalúe su modelo en la parte pequeña y en la muestra de frases malas. Determine si hay un umbral razonable que pase la mayoría de los nombres de ciudades, pero solo una pequeña cantidad de frases malas.

Yuval Filmus
fuente
Gracias. Había comenzado a buscar n-gram pero no sabía si estaba totalmente fuera de base, así que me alegra que lo hayas mencionado. La longitud de la palabra también suena interesante y algo en lo que no había pensado.
Andrew
Es posible que desee agregar frecuencia de caracteres a esto. En particular, eso debería deshacerse de todas las cosas numerosas. Una ventaja es que tales frecuencias son vectores de números que pueden ser entrenados / reconocidos en varios modelos estadísticos.
Raphael
1
@Raphael, la frecuencia de caracteres es la misma que la del análisis de gramo y, en general, el análisis de gramo es más fino que el análisis de gramas. 1n+1n
Yuval Filmus