En informática , la búsqueda aproximada de cadenas (a menudo denominada coloquialmente como búsqueda de cadenas difusas ) es la técnica de encontrar cadenas que coincidan con un patrón de forma aproximada (en lugar de hacerlo exactamente). El problema de la búsqueda aproximada de cadenas se divide normalmente 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]
Estas tres operaciones pueden generalizarse como formas de sustitución añadiendo 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]
Los distintos comparadores aproximados imponen distintas restricciones. Algunos utilizan un único coste global no ponderado, es decir, el número total de operaciones primitivas necesarias para convertir la coincidencia en el 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 única unidad de coste y el límite se establece en uno, foil , coils y oil contarán como coincidencias, mientras que foal 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 ponderaciones a diferentes operaciones. Algunos comparadores permiten asignaciones separadas de límites y ponderaciones a grupos individuales en el patrón.
Una posible definición del problema de correspondencia 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 , se calcula la distancia mínima de edición entre los primeros i 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 , 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 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 todos los i y j , podemos encontrar fácilmente una solución al problema original: es la subcadena para la que 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 utilizar el algoritmo de cálculo de distancia 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) para calcular E ( i , j ).
En la matriz que contiene los valores E ( x , y ), elegimos el valor mínimo en la última fila, sea E ( x 2 , y 2 ), y seguimos la ruta de cálculo hacia atrás, de regreso a la fila número 0. Si el campo al que llegamos fue 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 .
El cálculo de la matriz E ( x , y ) toma un tiempo O ( mn ) con el algoritmo de programación dinámica, mientras que la fase de trabajo inverso toma un tiempo O ( n + m ).
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. Por lo tanto, la idea es reducir la cantidad de pares de candidatos, en lugar de calcular la similitud de todos los pares de cadenas. Los algoritmos ampliamente utilizados se basan en verificación de filtros, hash, hash sensible a la localidad (LSH), 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 Map-Reduce) para realizar cálculos concurrentes.
Tradicionalmente, los algoritmos de comparación 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 buscar, pero no el texto. En otras palabras, las técnicas en línea realizan la búsqueda sin un índice. Los primeros algoritmos para la comparación aproximada en línea fueron sugeridos por Wagner y Fischer [3] y por Sellers [2] . Ambos algoritmos se basan en la programación dinámica pero resuelven diferentes problemas. 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 de diccionarios.
Las técnicas de búsqueda en línea han sido mejoradas en repetidas ocasiones. Quizás la mejora más famosa sea 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 núcleo de la utilidad de búsqueda de Unix agrep . 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 en grandes cantidades de datos 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 diversos algoritmos de indexación. Entre ellos se encuentran los árboles de sufijos , [5] los árboles métricos [6] y los 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, los 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 la coincidencia aproximada incluyen la corrección ortográfica . [5] 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 . [5] La vinculación de registros es una aplicación común donde se combinan 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. Requieren algoritmos diferentes, como la identificación acústica .
Una herramienta de línea de comandos común, fzf, se utiliza a menudo para integrar la búsqueda aproximada de cadenas en varias aplicaciones de línea de comandos. [10]
