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

Ответ 1

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

Я также написал связанную статью: поиск подстрок в потоках: небольшая модификация алгоритма Кнута-Морриса-Пратта в Haxe. В статье упоминается Jakarta RegExp, теперь ушедший в отставку и отдыхающий в Apache Attic. Библиотека 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"));

    }
}

Ответ 2

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

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

  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
  

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

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

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

Ответ 3

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

KMP по сути является быстрым способом построения DFA, совместимого с строкой, например, предложение Norman Ramsey # 2.

Ответ 4

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

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

Для простой реализации может быть Java 5 Scanner, который может принимать 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;
      }
}

Я думаю о регулярном выражении, потому что это похоже на задание для Finate State Automaton, которое начинается в исходном состоянии, изменяя символ состояния по символу, пока он не отклонит строку (нет соответствия) или попадет в состояние accept.

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

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

Ответ 5

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

Ответ 6

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

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

Теперь, если кто-то может придумать аналогичную реализацию, основанную на алгоритме поиска Knuth-Morris-Pratt, тогда у нас будет хорошая эффективное решение;)

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

Ответ 7

Внедрение скользящего окна. Сделайте свой буфер вокруг, переместите все элементы в буфере один вперед и введите один новый символ в буфер в конце. Если буфер равен вашему искомому слову, он содержится.

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

Ответ 8

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

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

Ответ 9

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

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. Я не вижу простого способа сделать это, кроме как приватная переменная для всего класса. В этом случае вы не должны указывать счет внутри этого метода.

Ответ 10

Если вы не привязаны к использованию 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 килобайт.

Ответ 11

Очень быстрый поиск потока реализуется в классе 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: Для получения дополнительной информации см. Ссылку .

Ответ 12

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

Ответ 13

Если вы ищете постоянную подстроку, а не регулярное выражение, я бы рекомендовал Boyer-Moore. В Интернете есть много исходного кода.

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

Майк.

Ответ 14

У меня также была аналогичная проблема: пропустить байты из InputStream до указанной строки (или массива байтов). Это простой код, основанный на циклическом буфере. Он не очень эффективен, но работает для моих нужд:

  private static boolean matches(int[] buffer, int offset, byte[] search) {
    final int len = buffer.length;
    for (int i = 0; i < len; ++i) {
      if (search[i] != buffer[(offset + i) % len]) {
        return false;
      }
    }
    return true;
  }

  public static void skipBytes(InputStream stream, byte[] search) throws IOException {
    final int[] buffer = new int[search.length];
    for (int i = 0; i < search.length; ++i) {
      buffer[i] = stream.read();
    }

    int offset = 0;
    while (true) {
      if (matches(buffer, offset, search)) {
        break;
      }
      buffer[offset] = stream.read();
      offset = (offset + 1) % buffer.length;
    }
  }

Ответ 15

Возможно, вы сможете реализовать очень быстрое решение с использованием Fast Fourier Transforms, которое, если оно выполнено правильно, позволит вам выполнить сопоставление строк в разы O (nlog (m)), где n - длина более длинной строки, быть согласованным, а m - длиной более короткой строки. Например, вы можете выполнить БПФ, как только вы получите поток ввода длины m, и если он будет соответствовать, вы можете вернуться, и если он не соответствует, вы можете выбросить первый символ в поток, подождать для появления нового символа через поток, а затем снова выполнить FFT.