stringtranslate.com

Métrica de cadena

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 coincidencia o comparación 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 triangular . Por ejemplo, las cadenas "Sam" y "Samuel" pueden considerarse 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 cadenas 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 y devuelve 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 ampliado para incluir métodos de comparaciones estadísticas fonéticas, basadas en tokens , gramaticales y de caracteres.

Las métricas de cadenas se utilizan ampliamente en la integración de información y actualmente se emplean 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 , búsqueda incremental , integración de datos , detección de malware , [3] e integración de conocimiento semántico .

Lista de métricas de cadenas

También existen funciones que miden la disimilitud entre cadenas, pero que no necesariamente cumplen la desigualdad triangular y, por lo tanto, no son métricas en el sentido matemático. Un ejemplo de este tipo de funciones es la distancia de Jaro-Winkler .

Ejemplos de medidas de cuerdas seleccionadas

Referencias

  1. ^ Lu, Jiaheng; et al. (2013). "Medidas de similitud de cadenas y uniones con sinónimos". Actas de la Conferencia internacional ACM SIGMOD de 2013 sobre gestión de datos . págs. 373–384. doi :10.1145/2463676.2465313. ISBN 9781450320375.S2CID2091942  .​
  2. ^ Navarro, Gonzalo (2001). "Una visita guiada para aproximar la correspondencia de cadenas". ACM Computing Surveys . 33 (1): 31–88. doi :10.1145/375360.375365. hdl : 10533/172862 . S2CID  207551224.
  3. ^ Shlomi Dolev ; Mohammad, Ghanayim; Alexander, Binun; Sergey, Frenkel; Yeali, S. Sun (2017). "Relación entre Jaccard y la distancia de edición en la agrupación de malware y la identificación en línea". 16.º Simposio Internacional IEEE sobre Computación en Red y Aplicaciones : 369–373.
  4. ^ abcde Métricas de cadenas de Sam - Lingüística computacional y fonética
  5. ^ Russell, David J., et al. "Una métrica de distancia basada en gramática permite la agrupación rápida y precisa de grandes conjuntos de secuencias 16S". BMC bioinformatics 11.1 (2010): 1-14.
  6. ^ Cohen, William; Ravikumar, Pradeep; Fienberg, Stephen (1 de agosto de 2003). "Una comparación de las métricas de distancia de cadenas para tareas de coincidencia de nombres": 73–78. {{cite journal}}: Requiere citar revista |journal=( ayuda )

Enlaces externos