Coincidencia aproximada de cadenas

En informática , la búsqueda aproximada de cadenas (a menudo denominada búsqueda difusa de cadenas ) es la técnica para encontrar cadenas que coincidan aproximadamente con un patrón (en lugar de exactamente). El problema de la búsqueda aproximada de cadenas se divide generalmente en dos subproblemas: encontrar coincidencias aproximadas de subcadenas dentro de una cadena dada y encontrar cadenas de diccionario que coincidan aproximadamente con el patrón.

La proximidad de una coincidencia se mide en términos del número de operaciones primitivas necesarias para convertir la cadena en una coincidencia exacta. Este número se denomina distancia de edición entre la cadena y el patrón. Las operaciones primitivas habituales son: ^{[ 1 ]}

• inserción: cot → co a t
• eliminación: co a t → cot
• sustitución: co a t → co s t

Estas tres operaciones pueden generalizarse como formas de sustitución añadiendo un carácter nulo (simbolizado aquí por *) dondequiera que se haya eliminado o insertado un carácter:

• inserción: co * t → co a t
• eliminación: co a t → co * t
• sustitución: co a t → co s t

Algunos comparadores aproximados también tratan la transposición , en la que se intercambian las posiciones de dos letras en la cadena, como una operación primitiva. ^{[ 1 ]}

• transposición: co st → co ts

Los distintos algoritmos de coincidencia aproximada imponen diferentes restricciones. Algunos utilizan un único coste global no ponderado, es decir, el número total de operaciones primitivas necesarias para convertir la coincidencia al patrón. Por ejemplo, si el patrón es coil , foil difiere en una sustitución, coils en una inserción, oil en una eliminación y foal en dos sustituciones. Si todas las operaciones cuentan como una sola unidad de coste y el límite se establece en uno, foil , coils y oil contarán como coincidencias, mientras que foal no lo hará.

Otros comparadores especifican el número de operaciones de cada tipo por separado, mientras que otros establecen un coste total pero permiten asignar diferentes ponderaciones a diferentes operaciones. Algunos comparadores permiten asignar límites y ponderaciones por separado a grupos individuales en el patrón.

Una posible definición del problema de coincidencia aproximada de cadenas es la siguiente: Dada una cadena patrón${\displaystyle P=p_{1}p_{2}...p_{m}}$y una cadena de texto${\displaystyle T=t_{1}t_{2}\dots t_{n}}$, encontrar una subcadena${\displaystyle T_{j',j}=t_{j'}\dots t_{j}}$en T , que, de todas las subcadenas de T , tiene la menor distancia de edición al patrón P.

Un enfoque de fuerza bruta sería calcular la distancia de edición a P para todas las subcadenas de T y luego elegir la subcadena con la distancia mínima. Sin embargo, este algoritmo tendría un tiempo de ejecución de O ( n ³ m ). 

Una mejor solución, propuesta por Sellers, ^{[ 2 ]} se basa en la programación dinámica . Utiliza una formulación alternativa del problema: para cada posición j en el texto T y cada posición i en el patrón P , calcular la distancia de edición mínima entre los primeros i caracteres del patrón,${\displaystyle P_{i}}$y cualquier subcadena${\displaystyle T_{j',j}}$de T que termina en la posición j .

Para cada posición j del texto T y cada posición i del patrón P , recorra todas las subcadenas de T que terminan en la posición j y determine cuál de ellas tiene la distancia de edición mínima a los primeros i caracteres del patrón P. Escriba esta distancia mínima como E ( i , j ). Después de calcular E ( i , j ) para todos los i y j , podemos encontrar fácilmente una solución al problema original: es la subcadena para la cual E ( m , j ) es mínima ( siendo m la longitud del patrón P ).   

Calcular E ( m , j ) es muy similar a calcular la distancia de edición entre dos cadenas. De hecho, podemos usar el algoritmo de cálculo de distancia de Levenshtein para E ( m , j ), con la única diferencia de que debemos inicializar la primera fila con ceros y guardar la ruta de cálculo, es decir, si usamos E ( i − 1, j ), E( i , j − 1) o E ( i − 1, j − 1) al calcular E ( i , j ).           

En el arreglo que contiene los valores E ( x , y ), luego elegimos el valor mínimo en la última fila, llamémoslo E ( x ₂ , y ₂ ), y seguimos el camino de cálculo hacia atrás, hasta el número de fila 0. Si el campo al que llegamos fue E (0, y ₁ ), entonces T [ y ₁ + 1] ... T [ y ₂ ] es una subcadena de T con la distancia de edición mínima al patrón P .       

El cálculo del array E ( x , y ) requiere un tiempo de O ( mn ) con el algoritmo de programación dinámica, mientras que la fase de trabajo inverso requiere un tiempo de O ( n + m ).   

También hay algoritmos cuyo tiempo de ejecución depende de k , un límite de la distancia de edición de interés, y son mejores cuando k es pequeño en relación con la longitud de las cadenas. En 1989, Landau y Vishkin dieron un${\displaystyle O(nk)}$algoritmo. Este algoritmo todavía se basa en la matriz de programación dinámica anterior, pero la llena de una manera ingeniosa, a lo largo de las diagonales. ^{[ 3 ]} En 2002, utilizando un algoritmo más complejo, Cole y Hariharan lograron una complejidad de${\displaystyle O({\frac {k^{4}}{m}}+n+m)}$. Tenga en cuenta que esto es mejor cuando${\displaystyle k^{3}\ll nm}$. ^{[ 4 ]}

El problema especializado de la coincidencia de patrones con k desajustes se define al no permitir inserciones ni eliminaciones en la coincidencia del patrón con el texto. Por lo tanto, la distancia de Hamming del patrón al segmento correspondiente del texto debe ser como máximo k . Este problema se ha resuelto con una complejidad de${\displaystyle O(n{\sqrt {k\log k}})}$. ^{[ 5 ]}

Otra idea reciente es la unión por similitud. Cuando la base de datos de coincidencia maneja una gran cantidad de datos, el tiempo O ( mn ) del algoritmo de programación dinámica no puede funcionar dentro de un tiempo limitado. Por lo tanto, la idea es reducir el número de pares candidatos, en lugar de calcular la similitud de todos los pares de cadenas. Los algoritmos más utilizados se basan en la verificación de filtros, el hashing, el hashing sensible a la localidad (LSH), los tries y otros algoritmos voraces y de aproximación. La mayoría de ellos están diseñados para adaptarse a algún marco (como MapReduce) para realizar cálculos concurrentes.

Tradicionalmente, los algoritmos de búsqueda aproximada de cadenas se clasifican en dos categorías: en línea y fuera de línea. Con los algoritmos en línea, el patrón se puede procesar antes de la búsqueda, pero el texto no. En otras palabras, las técnicas en línea realizan búsquedas sin un índice. Los primeros algoritmos para la búsqueda aproximada en línea fueron propuestos por Wagner y Fischer ^{[ 6 ]} y por Sellers ^{[ 2 ]} . Ambos algoritmos se basan en programación dinámica , pero resuelven problemas diferentes. El algoritmo de Sellers busca aproximadamente una subcadena en un texto, mientras que el algoritmo de Wagner y Fischer calcula la distancia de Levenshtein , siendo apropiado solo para la búsqueda difusa en diccionarios.

Las técnicas de búsqueda en línea se han perfeccionado repetidamente. Quizás la mejora más famosa sea el algoritmo bitap (también conocido como algoritmo 'shift-or' o 'shift-and'), que resulta muy eficiente para cadenas de patrones relativamente cortas. El algoritmo bitap es la base de la utilidad de búsqueda agrep de Unix . G. Navarro realizó una revisión de los algoritmos de búsqueda en línea. ^{[ 7 ]}

Aunque existen técnicas en línea muy rápidas, su rendimiento en grandes conjuntos de datos es deficiente. El preprocesamiento o la indexación de textos aceleran considerablemente la búsqueda. Actualmente, se han presentado diversos algoritmos de indexación. Entre ellos se encuentran los árboles de sufijos , ^{[ 8 ]} los árboles métricos ^{[ 9 ]} y los métodos de n -gramas . ^{[ 10 ] [ 11 ]} Navarro et al. ^{[ 10 ]} ofrecen un estudio detallado de las técnicas de indexación que permiten encontrar una subcadena arbitraria en un texto. Boytsov ^{[ 12 ]} ofrece un estudio computacional de los métodos de diccionario (es decir, métodos que permiten encontrar todas las palabras del diccionario que coinciden aproximadamente con un patrón de búsqueda).

Las aplicaciones comunes de coincidencia aproximada incluyen la corrección ortográfica . ^{[ 8 ]} Con la disponibilidad de grandes cantidades de datos de ADN, la coincidencia de secuencias de nucleótidos se ha convertido en una aplicación importante. ^{[ 1 ]} La coincidencia aproximada también se utiliza en el filtrado de spam . ^{[ 8 ]} La vinculación de registros es una aplicación común donde se comparan registros de dos bases de datos dispares.

La comparación de cadenas no se puede utilizar para la mayoría de los datos binarios, como imágenes y música. Para estos se requieren algoritmos diferentes, como la huella acústica .

Una herramienta común de línea de comandos fzfse usa a menudo para integrar la búsqueda aproximada de cadenas en varias aplicaciones de línea de comandos. ^{[ 13 ]}

• Proyecto Flamenco
• Proyecto de procesamiento eficiente de consultas de similitud con avances recientes en la coincidencia aproximada de cadenas basada en un umbral de distancia de edición.
• El proyecto StringMetric es una biblioteca Scala de métricas de cadenas y algoritmos fonéticos.
• Natural Project es una biblioteca de procesamiento del lenguaje natural en JavaScript que incluye implementaciones de métricas de cadenas populares.