De Wikipedia, la enciclopedia libre
Ir a navegaciónSaltar a buscar

En matemáticas y ciencias de la computación , una métrica de cadena (también conocida como métrica de similitud de cadena o función de distancia de cadena ) es una métrica que mide la distancia ("similitud inversa") entre dos cadenas de texto para la comparación o coincidencia aproximada de cadenas y en la búsqueda de cadenas difusas . Un requisito para una métrica de cadena (por ejemplo, en contraste con la coincidencia de cadenas ) es el cumplimiento de la desigualdad del triángulo . Por ejemplo, las cadenas "Sam" y "Samuel" se pueden considerar cercanas. [1] Una métrica de cadena proporciona un número que indica una indicación de distancia específica del algoritmo.

La métrica de cuerda más conocida es una rudimentaria llamada distancia de Levenshtein (también conocida como distancia de edición). [2] Opera entre dos cadenas de entrada, devolviendo un número equivalente al número de sustituciones y eliminaciones necesarias para transformar una cadena de entrada en otra. Las métricas de cadenas simplistas, como la distancia de Levenshtein, se han expandido para incluir métodos fonéticos, simbólicos , gramaticales y basados ​​en caracteres de comparaciones estadísticas.

Las métricas de cadenas se utilizan en gran medida en la integración de información y actualmente se utilizan en áreas que incluyen detección de fraude , análisis de huellas dactilares , detección de plagio , fusión de ontologías , análisis de ADN , análisis de ARN, análisis de imágenes , aprendizaje automático basado en evidencia , deduplicación de datos de bases de datos , minería de datos , incremental búsqueda , integración de datos , detección de malware [3] e integración de conocimiento semántico .

Lista de métricas de cadenas

Ejemplos de medidas de cadena seleccionadas

NombreEjemplo
Distancia de Hamming" ka rol in " y " ka thr in " es 3.
Distancia de Levenshtein y distancia de Damerau-Levenshteink itt e n y s itt i n g tienen una distancia de 3.
  1. k itten → s itten (sustitución de "s" por "k")
  2. sitt e n → sitt i n (sustitución de "i" por "e")
  3. sittin → sittin g (inserción de "g" al final).
Distancia Jaro-WinklerJaroWinklerDist ("MARTHA", "MARHTA") =
  • es el número de caracteres coincidentes ;
  • es la mitad del número de transposiciones ( "MARTHA"[3]!=H, "MARHTA"[3]!=T).
Personajes k más frecuentesMostFreqKeySimilarity (' r e s e a r ch', 's ee king', 2) = 2


Referencias

  1. ^ Lu, Jiaheng; et al. (2013). "La similitud de cadenas mide y se une con sinónimos" . Actas de la Conferencia Internacional ACM SIGMOD de 2013 sobre Gestión de Datos : 373–384. doi : 10.1145 / 2463676.2465313 . ISBN 9781450320375.
  2. ^ Navarro, Gonzalo (2001). "Una visita guiada para aproximar el emparejamiento de cuerdas". Encuestas de computación ACM . 33 (1): 31–88. doi : 10.1145 / 375360.375365 . hdl : 10533/172862 .
  3. ^ Shlomi Dolev ; Mohammad, Ghanayim; Alexander, Binun; Sergey, Frenkel; Yeali, S. Sun (2017). "Relación de Jaccard y distancia de edición en agrupamiento de malware e identificación online". 16º Simposio Internacional IEEE sobre Computación en Red y Aplicaciones : 369–373.
  4. ^ Cohen, William; Ravikumar, Pradeep; Fienberg, Stephen (1 de agosto de 2003). "Una comparación de métricas de distancia de cadenas para tareas de coincidencia de nombres" : 73–78. Cite journal requiere |journal=( ayuda )


Enlaces externos

  • https://web.archive.org/web/20070304092115/http://www.dcs.shef.ac.uk/~sam/stringmetrics.html#qgram Una descripción general bastante completa Índice de archivos en Wayback Machine
  • Biblioteca de código abierto de la Universidad Carnegie Mellon
  • StringMetric proyecta una biblioteca Scala de métricas de cadenas y algoritmos fonéticos
  • Proyecto natural una biblioteca de procesamiento de lenguaje natural de JavaScript que incluye implementaciones de métricas de cadenas populares