Algoritmos de búsqueda de cadenas para textos grandes con Java

1. Introducción

En este artículo, mostraremos varios algoritmos para buscar un patrón en un texto grande. Describiremos cada algoritmo con código proporcionado y antecedentes matemáticos simples.

Tenga en cuenta que los algoritmos proporcionados no son la mejor manera de realizar una búsqueda de texto completo en aplicaciones más complejas. Para hacer la búsqueda de texto completo correctamente, podemos usar Solr o ElasticSearch.

2. Algoritmos

Comenzaremos con un algoritmo de búsqueda de texto ingenuo que es el más intuitivo y ayuda a descubrir otros problemas avanzados asociados con esa tarea.

2.1. Métodos auxiliares

Antes de comenzar, definamos métodos simples para calcular números primos que usamos en el algoritmo de Rabin Karp:

public static long getBiggerPrime(int m) { BigInteger prime = BigInteger.probablePrime(getNumberOfBits(m) + 1, new Random()); return prime.longValue(); } private static int getNumberOfBits(int number) { return Integer.SIZE - Integer.numberOfLeadingZeros(number); } 

2.2. Búsqueda de texto simple

El nombre de este algoritmo lo describe mejor que cualquier otra explicación. Es la solución más natural:

public static int simpleTextSearch(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; int i = 0; while ((i + patternSize) = patternSize) return i; } i += 1; } return -1; }

La idea de este algoritmo es sencilla: iterar a través del texto y si hay una coincidencia para la primera letra del patrón, verifique si todas las letras del patrón coinciden con el texto.

Si m es un número de letras en el patrón y n es el número de letras en el texto, la complejidad temporal de estos algoritmos es O (m (nm + 1)) .

El peor de los casos ocurre en el caso de una cadena que tiene muchas ocurrencias parciales:

Text: baeldunbaeldunbaeldunbaeldun Pattern: baeldung

2.3. Algoritmo de Rabin Karp

Como se mencionó anteriormente, el algoritmo de búsqueda de texto simple es muy ineficiente cuando los patrones son largos y cuando hay muchos elementos repetidos del patrón.

La idea del algoritmo de Rabin Karp es utilizar hash para encontrar un patrón en un texto. Al comienzo del algoritmo, necesitamos calcular un hash del patrón que luego se usa en el algoritmo. Este proceso se denomina cálculo de huellas dactilares y podemos encontrar una explicación detallada aquí.

Lo importante del paso de preprocesamiento es que su complejidad de tiempo es O (m) y la iteración a través del texto tomará O (n), lo que da la complejidad de tiempo de todo el algoritmo O (m + n) .

Código del algoritmo:

public static int RabinKarpMethod(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; long prime = getBiggerPrime(patternSize); long r = 1; for (int i = 0; i < patternSize - 1; i++) { r *= 2; r = r % prime; } long[] t = new long[textSize]; t[0] = 0; long pfinger = 0; for (int j = 0; j < patternSize; j++) { t[0] = (2 * t[0] + text[j]) % prime; pfinger = (2 * pfinger + pattern[j]) % prime; } int i = 0; boolean passed = false; int diff = textSize - patternSize; for (i = 0; i <= diff; i++) { if (t[i] == pfinger) { passed = true; for (int k = 0; k < patternSize; k++) { if (text[i + k] != pattern[k]) { passed = false; break; } } if (passed) { return i; } } if (i < diff) { long value = 2 * (t[i] - r * text[i]) + text[i + patternSize]; t[i + 1] = ((value % prime) + prime) % prime; } } return -1; }

En el peor de los casos, la complejidad de tiempo para este algoritmo es O (m (n-m + 1)) . Sin embargo, en promedio, este algoritmo tiene una complejidad de tiempo O (n + m) .

Además, existe una versión Monte Carlo de este algoritmo que es más rápida, pero puede resultar en coincidencias incorrectas (falsos positivos).

2.4 Algoritmo de Knuth-Morris-Pratt

En el algoritmo de búsqueda de texto simple, vimos cómo el algoritmo podría ser lento si hay muchas partes del texto que coinciden con el patrón.

La idea del algoritmo de Knuth-Morris-Pratt es el cálculo de la tabla de turnos que nos proporciona la información donde debemos buscar nuestros candidatos a patrón.

Implementación Java del algoritmo KMP:

public static int KnuthMorrisPrattSearch(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; int[] shift = KnuthMorrisPrattShift(pattern); while ((i + patternSize) = patternSize) return i; } if (j > 0) { i += shift[j - 1]; j = Math.max(j - shift[j - 1], 0); } else { i++; j = 0; } } return -1; }

Y así es como calculamos la tabla de turnos:

public static int[] KnuthMorrisPrattShift(char[] pattern) { int patternSize = pattern.length; int[] shift = new int[patternSize]; shift[0] = 1; int i = 1, j = 0; while ((i + j) 
    
      0) { i = i + shift[j - 1]; j = Math.max(j - shift[j - 1], 0); } else { i = i + 1; j = 0; } } } return shift; }
    

La complejidad temporal de este algoritmo también es O (m + n) .

2.5. Algoritmo simple de Boyer-Moore

A dos científicos, Boyer y Moore, se les ocurrió otra idea. ¿Por qué no comparar el patrón con el texto de derecha a izquierda en lugar de izquierda a derecha, mientras mantiene la misma dirección de cambio?

public static int BoyerMooreHorspoolSimpleSearch(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; while ((i + patternSize) <= textSize) { j = patternSize - 1; while (text[i + j] == pattern[j]) { j--; if (j < 0) return i; } i++; } return -1; }

Como se esperaba, esto se ejecutará en tiempo O (m * n) . Pero este algoritmo condujo a la implementación de la ocurrencia y la heurística de coincidencia, lo que acelera significativamente el algoritmo. Podemos encontrar más aquí.

2.6. Algoritmo de Boyer-Moore-Horspool

Hay muchas variaciones de implementación heurística del algoritmo de Boyer-Moore, y la más simple es la variación de Horspool.

Esta versión del algoritmo se llama Boyer-Moore-Horspool, y esta variación resolvió el problema de los cambios negativos (podemos leer sobre el problema del cambio negativo en la descripción del algoritmo de Boyer-Moore).

Al igual que el algoritmo de Boyer-Moore, la complejidad del tiempo del peor de los casos es O (m * n) mientras que la complejidad promedio es O (n). El uso de espacio no depende del tamaño del patrón, sino solo del tamaño del alfabeto, que es 256, ya que ese es el valor máximo del carácter ASCII en el alfabeto inglés:

public static int BoyerMooreHorspoolSearch(char[] pattern, char[] text) { int shift[] = new int[256]; for (int k = 0; k < 256; k++) { shift[k] = pattern.length; } for (int k = 0; k < pattern.length - 1; k++){ shift[pattern[k]] = pattern.length - 1 - k; } int i = 0, j = 0; while ((i + pattern.length) <= text.length) { j = pattern.length - 1; while (text[i + j] == pattern[j]) { j -= 1; if (j < 0) return i; } i = i + shift[text[i + pattern.length - 1]]; } return -1; }

4. Conclusión

En este artículo, presentamos varios algoritmos para la búsqueda de texto. Dado que varios algoritmos requieren una base matemática más sólida, intentamos representar la idea principal debajo de cada algoritmo y proporcionarla de una manera simple.

Y, como siempre, el código fuente se puede encontrar en GitHub.