Java indexOf функции более эффективны, чем Рабин-Карп? Эффективность поиска текста

Question

Несколько недель назад я задал вопрос Stackoverflow о создании эффективного алгоритма для поиска шаблона в большом фрагменте текста.Прямо сейчас я использую функцию String indexOf для поиска.Одним из предложений было использование Рабина-Карпа в качестве альтернативы.Я написал небольшую тестовую программу для проверки реализации Рабина-Карпа следующим образом:

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);

}

И вот реализация Рабина-Карпа, которую я использую:

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

}

Реализация Rabin-Karp работает в том, что она возвращает правильное смещение строки, которую я ищу.Что меня удивляет, так это временная статистика, которая произошла, когда я запустил тестовую программу.Вот они:

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

Это было действительно удивительно.Мало того, что Рабин-Карп (по крайней мере, как это реализовано здесь) не быстрее, чем стандартная функция java indexOf String, он медленнее на порядок.Я не знаю, что не так (если что).У кого-нибудь есть мысли по этому поводу?

Спасибо,

Эллиот

Answer 1

Я ответил на этот вопрос ранее, и Эллиот указал, что я был просто неправ.Я извиняюсь перед сообществом.

В коде String.indexOf нет ничего волшебного.Это не изначально оптимизировано или что-то в этом роде.Вы можете скопировать метод indexOf из исходного кода String, и он будет запущен так же быстро.

Здесь мы видим разницу между эффективностью O () и фактической эффективностью.Рабин-Карп для строки длины N и шаблона длины M, Рабин-Карп равен O (N + M) и наихудший случай O (NM).Когда вы смотрите на это, String.indexOf () также имеет лучший регистр O (N + M) и худший регистр O (NM).

Если текст содержит много частичных совпадений с началомшаблон Рабина-Карпа останется близким к наилучшей производительности, в то время как String.indexOf - нет.Например, я тестировал приведенный выше код (на этот раз правильно :-)) на миллион '0', за которым следует один '1', а поиск 1000 '0' сопровождается одним '1'.Это вынудило String.indexOf работать в худшем случае.Для этого сильно вырожденного теста алгоритм Рабина-Карпа был примерно в 15 раз быстрее, чем indexOf.

Для текста на естественном языке Rabin-Karp останется близким к лучшему, а indexOf будет только слегка ухудшаться.Следовательно, решающим фактором является сложность операций, выполняемых на каждом шаге.

В самом внутреннем цикле indexOf сканирует соответствующий первый символ.На каждой итерации приходится:

• увеличить счетчик цикла
• выполнить два логических теста
• сделать один доступ к массиву

ВРабин-Карп на каждой итерации должен:

• увеличить счетчик цикла
• выполнить два логических теста
• сделать два доступа к массиву (фактически два вызова метода)
• обновить хеш, для чего требуется 9 числовых операций

Поэтому на каждой итерации Рабин-Карп будет отставать все дальше и дальше.Я попытался упростить алгоритм хеширования до просто символов XOR, но у меня все еще был дополнительный доступ к массиву и две дополнительные числовые операции, поэтому он был еще медленнее.

Кроме того, когда совпадение найдено, Рабин-Карп знает толькосовпадения хэшей и, следовательно, должны проверять каждый символ, в то время как indexOf уже знает совпадения с первым символом и, следовательно, имеет на один тест меньше.

Читая в Википедии, что Рабин-Карп используется для обнаружения плагиата, я взял БиблиюBook of Ruth убрал все знаки препинания и сделал все строчными, оставив чуть менее 10000 символов.Затем я искал «andthewomenherneighboursgaveitaname», который встречается в самом конце текста.String.indexOf был еще быстрее, даже с хэшем XOR.Однако если я исключил преимущество String.indexOfs, связанное с возможностью доступа к частному внутреннему массиву символов String, и заставил его скопировать массив символов, то, наконец, Рабин-Карп был действительно быстрее.

Однако я сознательно выбралэтот текст, как есть 213 "и" в Книге Рут и 28 "и".Если вместо этого я искал только последние символы «ursgaveitaname», то в тексте всего 3 «urs», поэтому indexOf возвращается ближе к своему лучшему случаю и снова выигрывает гонку.

В качестве более справедливого тестаЯ выбрал случайные 20 строк символов из второй половины текста и рассчитал их время.Рабин-Карп был примерно на 20% медленнее, чем алгоритм indexOf, работающий вне класса String, и на 70% медленнее, чем фактический алгоритм indexOf.Таким образом, даже в случае использования, для которого он предположительно подходит, он все еще был не лучшим выбором.

Так что же хорошего в Рабин-Карп?Независимо от длины или характера текста, который нужно найти, для каждого сравниваемого символа он будет медленнее.Независимо от того, какую хеш-функцию мы выберем, мы обязательно должны сделать дополнительный доступ к массиву и по крайней мере две числовые операции.Более сложная хеш-функция даст нам меньше ложных совпадений, но потребует больше числовых операторов.Рабин-Карп просто не может не отставать.

Как показано выше, если нам нужно найти совпадение с префиксом часто повторяющегося блока текста, indexOf может быть медленнее, но если мы знаем, что мы делаем это, это будет выглядеть так, как будто нам все-таки лучше использовать indexOf для поиска для текста без префикса, а затем проверьте, чтобы увидеть, присутствовал ли префикс.

Судя по моим сегодняшним исследованиям, я не вижу времени, когда дополнительная сложность Рабина Карпа окупится.

Answer 2

Здесь является источником для java.lang.String. indexOf это строка 1770.

Я подозреваю, что, поскольку вы используете его для такой короткой входной строки, дополнительные издержки алгоритма Рабина-Карпа над кажущейся наивной реализацией index.fring java.lang.String, вы не видите истинную производительность алгоритм. Я бы посоветовал попробовать его на более длинной входной строке для сравнения производительности.

Answer 3

Насколько я понимаю, Рабин Карп лучше всего использовать при поиске в блоке текста нескольких слов / фраз.

Подумайте о поиске плохого слова, чтобы пометить ненормативную лексику.

Если выЕсли у вас есть список из 2000 слов, включая производные, вам нужно будет вызвать indexOf 2000 раз, по одному на каждое слово, которое вы пытаетесь найти.

RabinKarp помогает с этим, выполняя поиск в обратном направлении.Создайте 4-х символьный хэш для каждого из 2000 слов и поместите его в словарь с помощью быстрого поиска.

Теперь для каждых 4 символов в тексте поиска выполните хеширование и проверку по словарю.

Как видите, теперь поиск выполняется наоборот - вместо этого мы ищем 2000 слов для возможного соответствия.Затем мы получаем строку из словаря и выполняем проверку на равенство.

Это также более быстрый поиск, поскольку мы ищем словарь, а не поиск по строке.

А теперь представьте худший сценарий выполнения всех этих поисков indexOf - самое последнее слово, которое мы проверяем, соответствует: ...

В статье в Википедии для RabinKarp, даже упоминаемой, есть неполноценность в описываемой вами ситуации.;-) http://en.wikipedia.org/wiki/Rabin-Karp_algorithm

Answer 4

Не вдаваясь в подробности, мне приходят на ум две причины:

• вы, вероятно, превзойдете стандартные реализации API только в очень особых случаях.Я не считаю, что «у Мэри был маленький ягненок, шерсть которого была бела, как снег» таким.
• Микробенчмаркинг очень сложен и может дать весьма обманчивые результаты. Вот объяснение , здесь список инструментов, которые вы можете использовать

Answer 5

Но это вполне естественно!
Ваш тестовый ввод в первую очередь слишком тривиален.

indexOf возвращает индекс was поиска в небольшом буфере (String внутренний массив char), в то время как Rabin-Karp должен выполнить предварительную обработку, чтобы настроить свои данные для работы, что занимает дополнительное время.

Чтобы увидеть разницу, вам нужно проверить действительно большой текст, чтобы найти выражения.

Также обратите внимание, что при использовании более изощренного алгоритма поиска строк они могут иметь «дорогую» настройку / предварительную обработку для обеспечения действительно быстрого поиска.
В вашем случае вы просто ищете was в предложении. В любом случае, вы всегда должны учитывать входные данные

Answer 6

Для такого рода поиска Кнут-Моррис-Пратт может работать лучше.В частности, если подстрока не просто повторяет символы, то KMP должен превосходить indexOf ().В худшем случае (строка из всех одинаковых символов) будет одинаковой.

Answer 7

Не только попробуйте более длинную статическую строку, но и попробуйте сгенерировать random длинные строки и каждый раз вставлять цель поиска в случайное место.Не рандомизируя его, вы увидите фиксированный результат для indexOf.

РЕДАКТИРОВАНИЕ: Случайное неверное понятие.Большая часть текста не является случайной.Но для эффективности вам потребуется много разных длинных строк, а не просто тестировать одну и ту же строку несколько раз.Я уверен, что есть способы извлечь "случайные" большие строки из еще большего источника текста или что-то в этом роде.