texto poner para notas como codigo bloc atributo algorithm text full-text-search relevance

algorithm - poner - codigo html para texto



¿Función que devuelve la afinidad entre los textos? (7)

considerar que tengo un

string1 = "hello hi goodmorning evening [...]"

y tengo algunas palabras clave menores

compare1 = "hello evening" compare2 = "hello hi"

Necesito una función que devuelva la afinidad entre el texto y las palabras clave. Ejemplo:

function(string1,compare1); // returns: 4 function(string1,compare2); // returns: 5 (more relevant)

Tenga en cuenta que 5 y 4 son solo por ejemplo.

Se podría decir - escribir una función que cuente las ocurrencias - pero para este ejemplo esto no funcionaría porque ambos obtuvieron 2 apariciones, pero compare1 es menos relevante porque "hello evening" no se encuentra exactamente en string1 (las 2 palabras hello y evening son más distante que hola hola)

¿Hay algún algoritmo conocido para hacer esto?

ADD1:

algos como Edit Distance en este caso NO funcionarían. Porque string1 es un texto completo (como 300-400 palabras) y las cadenas de comparación son max 4-5 word.

Eche un vistazo para crear N-grams a partir de sus datos de entrada y luego haga coincidir los N-grams. Tengo una solución donde considero cada n-grama como una dimensión en un espacio vectorial (que se convierte en un espacio de 4000 dimensiones en mi caso) y luego la afinidad es el coseno del ángulo entre dos vectores (el producto punto está involucrado aquí )

La parte más difícil es crear una métrica que defina la afinidad de la manera que desee.

Una alternativa es mirar una ventana deslizante y la puntuación en función de la cantidad de palabras en sus datos compare_x en la ventana. El puntaje final es la suma.

Aquí puede encontrar una lista de métricas para calcular la distancia entre cadenas, y una biblioteca javascript de código abierto que solo hace eso. http://en.wikipedia.org/wiki/String_metric En particular, eche un vistazo al algoritmo de Smith-Waterman, teniendo en cuenta que lo que ellos llaman "Alfabeto" puede estar compuesto por lo que llamamos Cuerdas: así, dado el alfabeto

{A = "hello", B = "hi",C = "goodmorning",D = "evening"}

y llamado d la distancia, tu función intenta calcular

d(ABCD,AB) vs d(ABCD,AC)

Bueno, puedes contar las ocurrencias de piezas del texto de comparación, es decir:

"abc" -> "a", "b", "c", "ab", "bc", "abc" (posible "ac", si así lo deseaba)

Y luego contar las ocurrencias de cada una de ellas, y sumarlas, posiblemente con un peso de (longitud de la cuerda) / (longitud de la cuerda entera).

Entonces solo necesitas una forma de producir esas piezas, y ejecutar un control para todas ellas.

Si bien la distancia de Levenshtein, tal como está, puede no ser adecuada para sus propósitos, una modificación de la misma podría: Intentar implementarla almacenando las inserciones, eliminaciones y sustituciones por separado.

La distancia será la suma de lo siguiente:

  • Todas las substucciones
  • La cantidad de espacios menos uno en cada conjunto de inserciones / eliminaciones consecutivas:
    • (En su caso: "Hola buena mañana" solo cuenta como dos ediciones, y ''[...]'' cuenta como uno).

Debería probar esto, por supuesto, pero si no funciona bien, intente simplemente usar la suma de inserciones / eliminaciones consecutivas (entonces, "hola buenos días" es solo 1 edición).

EDITAR

PD: esto supone un cambio relativamente importante en la forma en que funciona Levenshtein; primero querrá "alinear" sus datos (descubriendo dónde hay superposición significativa (más de dos caracteres) e insertando caracteres "nulos" que contarían como inserciones).

Además, esta es solo una idea no probada, por lo que cualquier idea de mejora es bienvenida.

Un algoritmo de programación dinámica

Parece que lo que estás buscando es muy similar a lo que hace el algoritmo de Smith-Waterman .

De la Wikipedia:

El algoritmo fue propuesto por primera vez por Temple F. Smith y Michael S. Waterman en 1981. Al igual que el algoritmo Needleman-Wunsch , del cual es una variación, Smith-Waterman es un algoritmo de programación dinámica . Como tal, tiene la propiedad deseable de que está garantizado encontrar la alineación local óptima con respecto al sistema de puntuación que se utiliza (que incluye la matriz de sustitución y el esquema de puntuación de brecha).

Veamos un ejemplo práctico, para que pueda evaluar su utilidad.

Supongamos que tenemos un texto:

text = "We the people of the United States, in order to form a more perfect union, establish justice, insure domestic tranquility, provide for the common defense, promote the general welfare, and secure the blessings of liberty to ourselves and our posterity, do ordain and establish this Constitution for the United States of America.";

Aislé el segmento que vamos a hacer coincidir, solo por su fácil lectura.

Compararemos la afinidad (o similitud) con una lista de cadenas:

list = { "the general welfare", "my personal welfare", "general utopian welfare", "the general", "promote welfare", " rulez" };

Tengo el algoritmo ya implementado, así que calcularé la similitud y normalizaré los resultados:

sw = SmithWatermanSimilarity[ text, #] & /@ list; swN = (sw - Min[sw])/(Max[sw] - Min[sw])

Luego trazamos los resultados:

Creo que es muy similar a tu resultado esperado.

HTH!

Algunas implementaciones (con código fuente)