java - instring - rabin karp algorithm

¿La función Java indexOf es más eficiente que Rabin-Karp? Eficiencia de búsqueda de texto

Question

Le hice una pregunta a Stackoverflow hace unas semanas sobre la creación de un algoritmo eficiente para buscar un patrón en una gran porción de texto. En este momento estoy usando el índice de la función StringOf para hacer la búsqueda. Una sugerencia fue utilizar Rabin-Karp como alternativa. Escribí un pequeño programa de prueba de la siguiente manera para probar una implementación de Rabin-Karp de la siguiente manera.

public static void main(String[] args) {
    String test = "Mary had a little lamb whose fleece was white as snow";

    String p = "was";
     long start  = Calendar.getInstance().getTimeInMillis();
     for (int x = 0; x < 200000; x++)
         test.indexOf(p);
     long end = Calendar.getInstance().getTimeInMillis();
     end = end -start;
     System.out.println("Standard Java Time->"+end);

    RabinKarp searcher = new RabinKarp("was");
    start  = Calendar.getInstance().getTimeInMillis();
    for (int x = 0; x < 200000; x++)
    searcher.search(test);
    end = Calendar.getInstance().getTimeInMillis();
    end = end -start;
    System.out.println("Rabin Karp time->"+end);

}

Y aquí está la implementación de Rabin-Karp que estoy usando:

import java.math.BigInteger;
import java.util.Random;

public class RabinKarp {
private String pat; // the pattern // needed only for Las Vegas
private long patHash; // pattern hash value
private int M; // pattern length
private long Q; // a large prime, small enough to avoid long overflow
private int R; // radix
private long RM; // R^(M-1) % Q
static private long dochash = -1L;

public RabinKarp(int R, char[] pattern) {
    throw new RuntimeException("Operation not supported yet");
}

public RabinKarp(String pat) {
    this.pat = pat; // save pattern (needed only for Las Vegas)
    R = 256;
    M = pat.length();
    Q = longRandomPrime();

    // precompute R^(M-1) % Q for use in removing leading digit
    RM = 1;
    for (int i = 1; i <= M - 1; i++)
        RM = (R * RM) % Q;
    patHash = hash(pat, M);
}

// Compute hash for key[0..M-1].
private long hash(String key, int M) {
    long h = 0;
    for (int j = 0; j < M; j++)
        h = (R * h + key.charAt(j)) % Q;
    return h;
}

// Las Vegas version: does pat[] match txt[i..i-M+1] ?
private boolean check(String txt, int i) {
    for (int j = 0; j < M; j++)
        if (pat.charAt(j) != txt.charAt(i + j))
            return false;
    return true;
}

// check for exact match
public int search(String txt) {
    int N = txt.length();
    if (N < M)
        return -1;
    long txtHash;
    if (dochash == -1L) {
        txtHash = hash(txt, M);
        dochash = txtHash;
    } else
        txtHash = dochash;

    // check for match at offset 0
    if ((patHash == txtHash) && check(txt, 0))
        return 0;

    // check for hash match; if hash match, check for exact match
    for (int i = M; i < N; i++) {
        // Remove leading digit, add trailing digit, check for match.
        txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
        txtHash = (txtHash * R + txt.charAt(i)) % Q;

        // match
        int offset = i - M + 1;
        if ((patHash == txtHash) && check(txt, offset))
            return offset;
    }

    // no match
    return -1; // was N
}

// a random 31-bit prime
private static long longRandomPrime() {
    BigInteger prime = new BigInteger(31, new Random());
    return prime.longValue();
}

// test client

}

La implementación de Rabin-Karp funciona porque devuelve el desplazamiento correcto de la cadena que estoy buscando. Sin embargo, lo que es sorprendente para mí son las estadísticas de sincronización que ocurrieron cuando ejecuté el programa de prueba. Aquí están:

Standard Java Time->39
Rabin Karp time->409

Esto fue realmente sorprendente. No solo Rabin-Karp (al menos como se implementa aquí) no es más rápido que la función estándar java indexOf String, es más lento en un orden de magnitud. No sé lo que está mal (en todo caso). ¿Alguien tiene pensamientos sobre esto?

Gracias,

Elliott

Answer 1

¡Pero esto es natural que suceda!
Su entrada de prueba es, en primer lugar, muy trivial.

indexOf devuelve el índice de búsqueda de un pequeño búfer ( String ''s internal char array`) mientras que Rabin-Karp tiene que hacer un preprocesamiento para configurar sus datos para que funcionen, lo que lleva más tiempo.

Para ver la diferencia, deberías probar en un texto realmente grande para encontrar expresiones.

También tenga en cuenta que al usar un algoritmo de búsqueda de cadenas más sofisticado, pueden tener una configuración / preprocesamiento "costoso" para proporcionar una búsqueda realmente rápida.
En su caso, solo buscaba una was en una oración. En cualquier caso, siempre debe tener en cuenta la entrada

Answer 2

No solo prueba una cadena estática más larga, sino que intenta generar cadenas largas aleatorias e insertando el objetivo de búsqueda en una ubicación aleatoria cada vez. Sin aleatorizarlo, verá un resultado fijo para indexOf .

EDITADO: el azar es el concepto equivocado. La mayoría del texto no es verdaderamente aleatorio. Pero necesitaría muchas cadenas largas diferentes para ser efectivas, y no solo probar la misma Cadena varias veces. Estoy seguro de que hay formas de extraer cadenas grandes "aleatorias" de una fuente de texto aún más grande, o algo así.

Answer 3

Aquí está la fuente de java.lang.String. indexOf es la línea 1770.

Sospecho que lo está utilizando en una cadena de entrada tan corta, la sobrecarga adicional del algoritmo de Rabin-Karp sobre la implementación ingenua del índice de Java de java.lang.String, no está viendo el verdadero rendimiento del algoritmo. Sugeriría probarlo en una cadena de entrada mucho más larga para comparar el rendimiento.

Answer 4

Respondí esta pregunta antes y Elliot me señaló que simplemente estaba equivocado. Me disculpo con la comunidad.

No hay nada mágico sobre el código String.indexOf. No está optimizado de forma nativa ni nada de eso. Puede copiar el método indexOf del código fuente String y se ejecuta igual de rápido.

Lo que tenemos aquí es la diferencia entre la eficacia de O () y la eficiencia real. Rabin-Karp para una cadena de longitud N y un patrón de longitud M, Rabin-Karp es O (N + M) y el peor caso de O (NM). Cuando lo analizas, String.indexOf () también tiene un mejor caso de O (N + M) y el peor caso de O (NM).

Si el texto contiene muchas coincidencias parciales al inicio del patrón, Rabin-Karp se mantendrá cerca de su mejor interpretación, mientras que String.indexOf no lo hará. Por ejemplo, probé el código anterior (correctamente esta vez :-)) en un millón de ''0 seguido de un único'' 1 '', y busqué 1000'' 0 seguidos por un único ''1''. Esto obligó a String.indexOf a su peor rendimiento de caso. Para esta prueba altamente degenerada, el algoritmo Rabin-Karp fue aproximadamente 15 veces más rápido que indexOf.

Para el texto en lenguaje natural, Rabin-Karp se mantendrá cerca del mejor de los casos y el indexOf solo se deteriorará ligeramente. El factor decisivo es, por lo tanto, la complejidad de las operaciones realizadas en cada paso.

En su bucle más interno, indexOf escanea para un primer personaje coincidente. En cada iteración debe:

• incrementar el contador de bucle
• realizar dos pruebas lógicas
• hacer un arreglo de acceso

En Rabin-Karp cada iteración tiene que:

• incrementar el contador de bucle
• realizar dos pruebas lógicas
• hacer dos accesos de matriz (en realidad dos invocaciones de método)
• actualizar un hash, que arriba requiere 9 operaciones numéricas

Por lo tanto, en cada iteración, Rabin-Karp caerá más y más atrás. Traté de simplificar el algoritmo hash solo para caracteres XOR, pero aún tenía acceso a un arreglo adicional y dos operaciones numéricas adicionales, por lo que era aún más lento.

Además, cuando se encuentra una coincidencia, Rabin-Karp solo conoce la coincidencia hash y, por lo tanto, debe probar cada carácter, mientras que indexOf ya conoce las coincidencias del primer carácter y, por lo tanto, tiene una prueba menos que hacer.

Después de leer en Wikipedia que Rabin-Karp se usa para detectar plagio, tomé el Libro de la Biblia de Ruth, eliminé toda la puntuación e hice que todo fuera minúscula, lo que dejó un poco menos de 10000 caracteres. Luego busqué "andthewomenherneighboursgaveitaname", que aparece cerca del final del texto. String.indexOf fue aún más rápido, incluso con solo el hash XOR. Sin embargo, si eliminé la ventaja de String.indexOfs de poder acceder a la matriz de caracteres internos privados de String y forzarla a copiar la matriz de caracteres, entonces, finalmente, Rabin-Karp fue realmente más rápido.

Sin embargo, deliberadamente elegí ese texto ya que hay 213 "y" s en el Libro de Ruth y 28 "y el" s ". Si, en cambio, busqué solo los últimos caracteres "ursgaveitaname", bueno, solo hay 3 "urs" en el texto, por lo que indexOf vuelve más cerca de su mejor caso y gana la carrera nuevamente.

Como prueba más justa elegí cadenas de 20 caracteres al azar de la segunda mitad del texto y los sincronicé. Rabin-Karp fue aproximadamente un 20% más lento que el algoritmo indexOf que se ejecuta fuera de la clase String, y un 70% más lento que el algoritmo indexOf real. Por lo tanto, incluso en el caso de uso para el que supuestamente es apropiado, todavía no era la mejor opción.

Entonces, ¿de qué sirve Rabin-Karp? No importa la longitud o la naturaleza del texto que se buscará, en cada personaje comparado será más lento. No importa qué función hash elijamos, seguramente estamos obligados a hacer un acceso adicional al arreglo y al menos dos operaciones numéricas. Una función hash más compleja nos dará menos coincidencias falsas, pero requiere más operadores numéricos. Simplemente no hay forma de que Rabin-Karp pueda mantenerse al día.

Como se demostró anteriormente, si necesitamos encontrar una coincidencia prefijada por un bloque de texto que se repite a menudo, indexOf puede ser más lento, pero si sabemos que lo estamos haciendo, parecería que todavía estaríamos mejor usando indexOf para buscar el texto. sin el prefijo y luego verifica si el prefijo estaba presente.

Basado en mis investigaciones de hoy, no puedo ver ningún momento en el que la complejidad adicional de Rabin Karp valga la pena.

Answer 5

Desde mi punto de vista, Rabin Karp se usa mejor cuando se busca un bloque de texto para palabras / frases mutiples.

Piense en una mala búsqueda de palabras, para marcar un lenguaje abusivo.

Si tiene una lista de 2000 palabras, incluidas derivaciones, deberá llamar al índice de 2000 veces, una por cada palabra que está tratando de encontrar.

RabinKarp ayuda con esto haciendo la búsqueda al revés. Haz un hash de 4 caracteres de cada una de las 2000 palabras y ponlo en un diccionario con una búsqueda rápida.

Ahora, para cada 4 caracteres del texto de búsqueda, compruebe y compruebe el diccionario.

Como puede ver, la búsqueda ahora es al revés: estamos buscando las 2000 palabras para una posible coincidencia. Luego obtenemos la cadena del diccionario y hacemos un igual para verificar para estar seguros.

También es una búsqueda más rápida de esta manera, porque estamos buscando un diccionario en lugar de buscar coincidencias de cadenas.

Ahora, imagina el peor escenario posible de hacer todas esas búsquedas en el índice de búsqueda: la ÚLTIMA palabra que verificamos es una coincidencia ...

El artículo de Wikipedia para RabinKarp incluso menciona la inferioridad en la situación que describes. ;-) http://en.wikipedia.org/wiki/Rabin-Karp_algorithm

Answer 6

Para este tipo de búsqueda, Knuth-Morris-Pratt puede tener un mejor rendimiento. En particular, si la subcadena no solo repite caracteres, entonces KMP debe superar a indexOf (). El peor caso (cadena de todos los mismos caracteres) será el mismo.

Answer 7

Sin buscar detalles, dos razones vienen a mi mente:

• Es muy probable que supere las implementaciones estándar de API solo en casos muy especiales. No considero que "María tuvo un corderito cuyo vellón era blanco como la nieve" para ser tal.
• la microanalización es muy difícil y puede dar resultados bastante engañosos. Aquí hay una explicación , aquí una lista de herramientas que podrías usar