En informática , la coincidencia aproximada de cadenas (a menudo denominada coloquialmente búsqueda de cadenas difusas ) es la técnica de encontrar cadenas que coincidan con un patrón aproximadamente (en lugar de exactamente). El problema de la coincidencia aproximada de cadenas se suele dividir en dos subproblemas: encontrar coincidencias aproximadas de subcadenas dentro de una cadena determinada y encontrar cadenas de diccionario que coincidan aproximadamente con el patrón.
La cercanía 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 llama distancia de edición entre la cuerda y el patrón. Las operaciones primitivas habituales son: [1]
Estas tres operaciones se pueden generalizar como formas de sustitución agregando un carácter NULO (aquí simbolizado por *) dondequiera que se haya eliminado o insertado un carácter:
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]
Diferentes comparadores aproximados imponen diferentes restricciones. Algunos comparadores utilizan un único costo 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 espiral , el papel de aluminio difiere en una sustitución, las espirales en una inserción, el aceite en una eliminación y el potro en dos sustituciones. Si todas las operaciones cuentan como una sola unidad de costo y el límite se establece en uno, el papel de aluminio , las bobinas y el aceite contarán como fósforos, mientras que el potro no.
Otros comparadores especifican el número de operaciones de cada tipo por separado, mientras que otros establecen un costo total pero permiten asignar diferentes pesos a diferentes operaciones. Algunos comparadores permiten asignaciones separadas de límites y pesos a grupos individuales en el patrón.
Una posible definición del problema de coincidencia aproximada de cadenas es la siguiente: dada una cadena de patrón y una cadena de texto , encuentre una subcadena en T que, de todas las subcadenas de T , tenga la distancia de edición más pequeña 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 O ( n 3 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 , calcule la distancia de edición mínima entre los i primeros caracteres del patrón, y cualquier subcadena de T que termine en la posición j .
Para cada posición j en el texto T y cada posición i en el patrón P , revise 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 hasta los i primeros caracteres del patrón P. Escriba esta distancia mínima como E ( i , j ). Después de calcular E ( i , j ) para todo 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 distancias de Levenshtein para E ( m , j ), la única diferencia es 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 la matriz que contiene los valores de E ( x , y ), luego elegimos el valor mínimo en la última fila, sea E ( x 2 , y 2 ), y seguimos el camino de cálculo hacia atrás, de regreso a la fila número 0. Si el campo al que llegamos era E (0, y 1 ), entonces T [ y 1 + 1] ... T [ y 2 ] es una subcadena de T con la distancia de edición mínima al patrón P.
Calcular la matriz E ( x , y ) toma O ( mn ) tiempo con el algoritmo de programación dinámica, mientras que la fase de trabajo hacia atrás toma O ( n + m ) tiempo.
Otra idea reciente es la unión por similitud. Cuando la base de datos coincidente se relaciona con una gran escala de datos, el tiempo O ( mn ) con el algoritmo de programación dinámica no puede funcionar dentro de un tiempo limitado. Entonces, la idea es reducir el número de pares candidatos, en lugar de calcular la similitud de todos los pares de cadenas. Los algoritmos ampliamente utilizados se basan en la verificación de filtros, el hash, el hash sensible a la localidad (LSH), los intentos y otros algoritmos codiciosos y de aproximación. La mayoría de ellos están diseñados para adaptarse a algún marco (como Map-Reduce) para calcular simultáneamente.
Tradicionalmente, los algoritmos de coincidencia aproximada de cadenas se clasifican en dos categorías: en línea y fuera de línea. Con algoritmos en línea, el patrón se puede procesar antes de realizar la búsqueda, pero el texto no. En otras palabras, las técnicas en línea realizan búsquedas sin índice. Wagner y Fischer [3] y Sellers sugirieron los primeros algoritmos para la coincidencia aproximada en línea . [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 sólo para búsqueda difusa por diccionario.
Las técnicas de búsqueda en línea se han mejorado repetidamente. Quizás la mejora más famosa es el algoritmo bitap (también conocido como algoritmo shift-or y shift-and), que es muy eficiente para cadenas de patrones relativamente cortas. El algoritmo Bitap es el corazón de la utilidad de búsqueda agrep de Unix . G. Navarro realizó una revisión de los algoritmos de búsqueda en línea. [4]
Aunque existen técnicas en línea muy rápidas, su rendimiento con datos de gran tamaño es inaceptable. El preprocesamiento o indexación de texto hace que la búsqueda sea mucho más rápida. Hoy en día, se han presentado una variedad de algoritmos de indexación. Entre ellos se encuentran árboles de sufijos , [5] árboles métricos [6] y métodos de n-gramas . [7] [8] Navarro et al. ofrecen un estudio detallado de las técnicas de indexación que permiten encontrar una subcadena arbitraria en un texto . [7] Boytsov 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). [9]
Las aplicaciones comunes de concordancia aproximada incluyen la revisión ortográfica . [5] Con la disponibilidad de grandes cantidades de datos de ADN, la comparación 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 . [5] La vinculación de registros es una aplicación común en la que se comparan registros de dos bases de datos distintas.
La coincidencia de cadenas no se puede utilizar para la mayoría de los datos binarios, como imágenes y música. Requieren diferentes algoritmos, como la toma de huellas acústicas .
A menudo se utiliza una herramienta de línea de comandos común, fzf, para integrar la búsqueda de cadenas aproximadas en varias aplicaciones de línea de comandos. [10]
