Cómo determinar una cadena de ADN para la semejanza a otra

Question

Espero que estoy redactando esto correctamente para transmitir lo que estoy buscando.

Necesito comparar dos textos. Si las dos cadenas son iguales, me gustaría obtener puntajes que sean muy parecidos, si las cuerdas son muy diferentes, necesito puntajes muy diferentes.

Si tomo un hash md5 de un correo electrónico y cambio un carácter, el hash cambia drásticamente. Quiero que algo no cambie demasiado. Necesito comparar cómo se parecen dos piezas de contenido sin almacenar la cadena.

Actualización: Estoy buscando ahora la combinación de algunas ideas de los diversos enlaces que las personas han proporcionado. Idealmente, me gustaría tener una sola función de entrada para crear mi puntaje, así que estoy buscando usar una cadena de referencia para comparar siempre mi entrada. También estoy buscando tomar personajes asci y sugerirlos. Todavía leyendo todos los enlaces provistos.

Answer 1

Lo que está buscando es un algoritmo LCS (vea también Levenshtein distance). También puede probar Soundex o algún otro phonetic algorithm.

Answer 2

comprobar su Levenshtein Distance

En PHP que incluso tienen la levenshtein() function que hace exactamente eso.

Answer 3

Necesito comparar dos textos. Si las dos cadenas son iguales, me gustaría obtener puntajes que sean muy parecidos, si las cuerdas son muy diferentes, necesito puntajes muy diferentes.

Realmente depende de lo que quiere decir con "igual" o "diferente". Por ejemplo, si alguien reemplaza a "Estados Unidos de América" ​​con "EE. UU." En su cadena, es la misma cadena (porque EE. UU. Es solo una abreviación de algo más), o es muy diferente (porque muchos caracteres cambiaron)?

Esencialmente necesita diseñar una función que describa cómo calcular "uniformidad" o utilice una definición preexistente de la misma. Por ejemplo, la susodicha Levenshtein distance mide la diferencia total en función de la cantidad de cambios que debe realizar para llegar a la cadena original.

Answer 4

Dado que la distancia de Levenshtein necesita ambas cadenas de entrada para producir un valor, debería almacenar todas las cadenas.

Sin embargo, podría utilizar un pequeño número de cadenas como marcadores y almacenarlas solo como cadenas.

Luego, calcula la distancia de Levenshtein de una nueva cadena a cada una de estas cadenas de marcadores y almacena estos valores. Entonces podría adivinar que dos cadenas que tienen una distancia Levenshtein similar a todos los marcadores también son similares entre sí. Es probable que sea sensato "diseñar" estos marcadores de forma tal que su distancia mutua de Levenshtein sea lo más grande posible. No sé si ha habido alguna investigación en esta dirección.

Answer 5

Muchas personas han sugerido buscar enfoques a distancia/métricos, y creo que la redacción de la pregunta lo lleva de esa manera. (Por cierto, un hash como md5 intenta hacer lo contrario que una métrica, por lo que no es sorprendente que esto no funcione para usted.Hay ideas similares que no cambian mucho en pequeños deltas, pero sospecho que no codifican suficiente información para lo que quiere hacer)

Sin embargo, dada su actualización en los comentarios, creo que este tipo de enfoque no es muy útil

Lo que está buscando es más un problema de agrupamiento, donde desea generar una firma (es decir, un vector de característica) de cada correo electrónico y luego compararlo con nuevas entradas. Entonces, esencialmente, lo que tienes es un problema de aprendizaje automático. Decidir qué significa "cerrar" puede ser un desafío. Sin embargo, para empezar, suponiendo que en realidad son los correos electrónicos que está mirando, puede ser útil observar el tipo de generación de características realizada por muchos filtros de correo no deseado, esto le dará (probablemente un espacio euclidiano, al menos para comenzar) un espacio para medir distancias en función de una firma (vector de características).

Sin saber más acerca de su problema, es difícil ser más específico.

Answer 6

Al leer sus comentarios, parece que en realidad está tratando de comparar documentos completos, cada uno con muchas palabras.

Esto se hace con éxito en sistemas de recuperación de información por treating documents as N-dimensional points in space. Cada palabra en el lenguaje es un eje. La distancia a lo largo del eje está determinada por la cantidad de veces que aparece esa palabra en el documento. Documentos similares están entonces "cerca" el uno del otro en el espacio.

De esta manera, no es necesario almacenar todo el documento, solo cuenta la palabra. Y, por lo general, las palabras más comunes en el idioma no se cuentan en absoluto.