Una posible definición del problema de coincidencia aproximada de cadena es la siguiente: Dado un patrón de cadena P = p 1 p 2 . . . p m {\displaystyle P = p_{1}p_{2}…p_{m}}
y una cadena de texto T = t 1 t 2 t t n {\displaystyle T=t_{1}t_{2}\dots t_{n}}
, encuentre una subcadena T j ‘, j = t j ‘t t j {\displaystyle T_{j’,j}=t_{j’}\dots t_{j}}
en T, que, de todas las subcadenas de T, tiene 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 el tiempo de ejecución O(n3 m).
Una solución mejor, que fue propuesta por los vendedores, 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 mínima de edición entre los primeros caracteres i del patrón, P i {\displaystyle P_{i}}
, y cualquier subcadena T j ‘, j {\displaystyle T_{j’,j}}
de T que termina en la posición j.
Para cada posición j en el texto T, y cada posición i en el patrón P, vaya a través de todas las subcadenas de T que terminan en la posición j, y determine cuál de ellas tiene la distancia mínima a los primeros caracteres i 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 que E(m, j) es mínima (m es 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), 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) en la computación E(i, j).
En la matriz que contiene los valores E(x, y), luego elegimos el valor mínimo en la última fila, lo dejamos ser E(x2, y2), y seguimos la ruta de cálculo hacia atrás, de vuelta al número de fila 0. Si el campo al que llegamos fue E(0, y1), entonces T … T es una subcadena de T con la distancia mínima de edición al patrón P.
El cálculo de la matriz E(x, y) toma tiempo O(mn) con el algoritmo de programación dinámica, mientras que la fase de trabajo hacia atrás toma tiempo O(n + m).
Otra idea reciente es la unión de similitud. Cuando la base de datos 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, en lugar de calcular la similitud de todos los pares de cadenas, reducir el número de pares candidatos. Los algoritmos ampliamente utilizados se basan en verificación de filtros, hashing, hashing sensible a la localidad (LSH), Intentos y otros algoritmos codiciosos y de aproximación. La mayoría de ellos están diseñados para adaptarse a algún marco de trabajo (como Map-Reduce) para calcular simultáneamente.