Эффективный способ поиска потока для строки - PullRequest
Новая
       15

Эффективный способ поиска потока для строки

48 голосов
/ 11 мая 2009

Давайте предположим, что у вас есть поток текста (или Reader на Java), который я хотел бы проверить на наличие определенной строки. Поток текста может быть очень большим, поэтому, как только строка поиска будет найдена, я хотел бы вернуть значение true, а также попытаться избежать сохранения всего ввода в памяти.

Наивно, я мог бы попытаться сделать что-то вроде этого (на Java): 

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    while((numCharsRead = reader.read(buffer)) > 0) {
        if ((new String(buffer, 0, numCharsRead)).indexOf(searchString) >= 0)
            return true;
    }
    return false;
}

Конечно, это не может обнаружить данную строку поиска, если это происходит на границе буфера 1k:

Поиск текста: "stackoverflow"
Потоковый буфер 1: «abc ......... стек»
Потоковый буфер 2: «переполнение ....... xyz»

Как я могу изменить этот код так, чтобы он правильно находил заданную строку поиска через границу буфера, но без загрузки всего потока в память?

Редактировать: Обратите внимание, что при поиске строки для потока мы пытаемся минимизировать количество операций чтения из потока (чтобы избежать задержки в сети / диске) и сохранить постоянную загрузку памяти независимо от объема данных в потоке. Фактическая эффективность алгоритма сопоставления строк является вторичной, но, очевидно, было бы неплохо найти решение, которое использовало бы один из наиболее эффективных из этих алгоритмов.

Ответы [ 15 ]

14 голосов
/ 11 мая 2009

Здесь есть три хороших решения:

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

    String needle;
n = needle.length();

for every input character c do
  add index 0 to the list
  for every index i in the list do
    if c == needle[i] then
      if i + 1 == n then
        return true
      else
        replace i in the list with i + 1
      end
    else
      remove i from the list
    end
  end
end

    Это найдет строку, если она существует, и вам никогда не понадобится буфер.

  2. Немного больше работы, но и быстрее: выполните преобразование NFA в DFA, которое заранее определит, какие списки индексов возможны, и присвойте каждому из них небольшое целое число. (Если вы читаете о поиске строк в Википедии, это называется конструкция powerset .) Тогда у вас есть одно состояние, и вы делаете переход между состояниями для каждого входящего символа. Нужный вам NFA - это просто DFA для строки, которой предшествует состояние, которое недетерминировано либо удаляет символ, либо пытается использовать текущий символ. Вам также понадобится явное состояние ошибки.

  3. Если вам нужно что-то более быстрое, создайте буфер, размер которого как минимум в два раза больше n, и пользователь Boyer-Moore для компиляции конечного автомата из needle. У вас будет много лишних хлопот, потому что Бойера-Мура не так просто реализовать (хотя вы найдете код в Интернете) и потому, что вам нужно будет организовать перемещение строки через буфер. Вам придется создать или найти кольцевой буфер, который может «скользить» без копирования; в противном случае вы, скорее всего, вернете любой выигрыш в производительности, полученный от Бойера-Мура.

9 голосов
/ 22 января 2013

Я сделал несколько изменений в алгоритме Кнута Морриса Пратта для частичных поисков. Поскольку фактическая позиция сравнения всегда меньше или равна следующей, дополнительная память не требуется. Код с Makefile также доступен на github и написан на Haxe для одновременной работы с несколькими языками программирования, включая Java.

Я также написал статью по теме: поиск подстрок в потоках: небольшая модификация алгоритма Кнута-Морриса-Пратта в Haxe . В статье упоминается Джакарта RegExp , теперь вышедшая на пенсию и отдыхающая на чердаке Apache. Метод библиотеки Jakarta Regexp « match » в классе RE использует CharacterIterator в качестве параметра. 

class StreamOrientedKnuthMorrisPratt {
    var m: Int;
    var i: Int;
    var ss:
    var table: Array<Int>;

    public function new(ss: String) {
        this.ss = ss;
        this.buildTable(this.ss);
    }

    public function begin() : Void {
        this.m = 0;
        this.i = 0;
    }

    public function partialSearch(s: String) : Int {
        var offset = this.m + this.i;

        while(this.m + this.i - offset < s.length) {
            if(this.ss.substr(this.i, 1) == s.substr(this.m + this.i - offset,1)) {
                if(this.i == this.ss.length - 1) {
                    return this.m;
                }
                this.i += 1;
            } else {
                this.m += this.i - this.table[this.i];
                if(this.table[this.i] > -1)
                    this.i = this.table[this.i];
                else
                    this.i = 0;
            }
        }

        return -1;
    }

    private function buildTable(ss: String) : Void {
        var pos = 2;
        var cnd = 0;

        this.table = new Array<Int>();
        if(ss.length > 2)
            this.table.insert(ss.length, 0);
        else
            this.table.insert(2, 0);

        this.table[0] = -1;
        this.table[1] = 0;

        while(pos < ss.length) {
            if(ss.substr(pos-1,1) == ss.substr(cnd, 1))
            {
                cnd += 1;
                this.table[pos] = cnd;
                pos += 1;
            } else if(cnd > 0) {
                cnd = this.table[cnd];
            } else {
                this.table[pos] = 0;
                pos += 1;
            }
        }
    }

    public static function main() {
        var KMP = new StreamOrientedKnuthMorrisPratt("aa");
        KMP.begin();
        trace(KMP.partialSearch("ccaabb"));

        KMP.begin();
        trace(KMP.partialSearch("ccarbb"));
        trace(KMP.partialSearch("fgaabb"));

    }
}
9 голосов
/ 11 мая 2009

Алгоритм поиска Кнута-Морриса-Пратта никогда не копирует; это просто свойство, которое вы хотите для поиска в потоке. Я использовал его ранее для этой проблемы, хотя могут быть более простые способы использования доступных библиотек Java. (Когда это подошло ко мне, я работал в C в 90-х.)

KMP по сути является быстрым способом создания DFA, соответствующего строке, как предложение Нормана Рэмси №2.

5 голосов
/ 11 мая 2009

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

Если вы ограничены ограничением использования постоянной памяти, Java хранит массивы любого типа в куче, и, таким образом, обнуление ссылки не освобождает память никоим образом; Я думаю, что любое решение, включающее массивы в цикле, потребляет память в куче и требует GC.

Для простой реализации, возможно, * 5 * * Сканер Java 5, который может принимать InputStream и использовать java.util.regex.Pattern для поиска входных данных, может избавить вас от беспокойства о реализации подробности.

Вот пример потенциальной реализации: 

public boolean streamContainsString(Reader reader, String searchString)
            throws IOException {
      Scanner streamScanner = new Scanner(reader);
      if (streamScanner.findWithinHorizon(searchString, 0) != null) {
        return true;
      } else {
        return false;
      }
}

Я думаю, что это регулярное выражение, потому что это звучит как работа для автомата с конечным состоянием, который начинается в начальном состоянии, меняется состояние за символом, пока не отклонит строку (без совпадения) или не перейдет в состояние принятия.

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

Это также, как работают регулярные выражения.

4 голосов
/ 12 мая 2009

Я считаю, что лучшее решение этой проблемы - постараться сделать ее проще. Помните, потому что я читаю из потока, я хочу, чтобы количество чтений из потока было минимальным (поскольку задержка сети или диска может быть проблемой), в то же время сохраняя объем используемой памяти постоянным (так как поток может быть очень большой по размеру). Фактическая эффективность сопоставления строк не является целью номер один (так как это было изучено до смерти уже).

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

Теперь, если кто-то может придумать похожую реализацию, основанную на алгоритме поиска Кнута-Морриса-Пратта , тогда у нас будет хорошее эффективное решение;) 

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
    char[] buffer = new char[1024];
    int numCharsRead;
    int count = 0;
    while((numCharsRead = reader.read(buffer)) > 0) {
        for (int c = 0; c < numCharsRead; c++) {
            if (buffer[c] == searchString.charAt(count))
                count++;
            else
                count = 0;
            if (count == searchString.length()) return true;
        }
    }
    return false;
}
4 голосов
/ 11 мая 2009

Вместо того, чтобы ваш буфер был массивом, используйте абстракцию, которая реализует кольцевой буфер . Ваш расчет индекса будет buf[(next+i) % sizeof(buf)], и вам нужно быть осторожным, чтобы заполнить буфер половиной за раз. Но пока строка поиска помещается в половину буфера, вы ее найдете.

1 голос
/ 20 января 2013

Очень быстрый поиск потока реализован в классе RingBuffer из среды Ujorm. Смотрите образец: 

 Reader reader = RingBuffer.createReader("xxx ${abc} ${def} zzz");

 String word1 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("abc", word1);

 String word2 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("def", word2);

 String word3 = RingBuffer.findWord(reader, "${", "}");
 assertEquals("", word3);

Реализация одного класса доступна на SourceForge : Для получения дополнительной информации см. Ссылку .

.
1 голос
/ 11 мая 2009

Если вы не привязаны к использованию Reader, вы можете использовать Java NIO API для эффективной загрузки файла. Например (не проверено, но должно быть близко к работе): 

public boolean streamContainsString(File input, String searchString) throws IOException {
    Pattern pattern = Pattern.compile(Pattern.quote(searchString));

    FileInputStream fis = new FileInputStream(input);
    FileChannel fc = fis.getChannel();

    int sz = (int) fc.size();
    MappedByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, sz);

    CharsetDecoder decoder = Charset.forName("UTF-8").newDecoder();
    CharBuffer cb = decoder.decode(bb);

    Matcher matcher = pattern.matcher(cb);

    return matcher.matches();
}

По сути, это mmap () - файл для поиска, и он полагается на операционную систему, которая делает правильные шаги в отношении использования кеша и памяти. Однако обратите внимание, что map () дороже, чем просто чтение файла в большой буфер для файлов размером менее 10 КиБ.

1 голос
/ 11 мая 2009

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

public boolean streamContainsString(Reader reader, String searchString) throws IOException {
char[] buffer = new char[1024];
int numCharsRead;
int count = 0;
while((numCharsRead = reader.read(buffer)) > 0) {
    if (buffer[numCharsRead -1] == searchString.charAt(count))
        count++;
    else
        count = 0;

    if (count == searchString.size())    
     return true;
}
return false; 
}

Единственная проблема - когда вы просматриваете символы ... в этом случае должен быть способ запоминания вашей переменной count. Я не вижу простого способа сделать это, кроме как в качестве закрытой переменной для всего класса. В этом случае вы не будете создавать счетчик внутри этого метода.

1 голос
/ 11 мая 2009

Я думаю, вам нужно буферизовать небольшое количество на границе между буферами.

Например, если размер вашего буфера равен 1024, а длина строки SearchString равна 10, тогда, кроме поиска в каждом 1024-байтовом буфере, вам также необходимо искать каждый 18-байтовый переход между двумя буферами (9 байтов с конца предыдущий буфер объединяется с 9 байтами от начала следующего буфера).

Страница:
...