Алгоритм подсчета появления строк

Question

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

Из того, что я прочитал , алгоритм поиска строки Бойера-Мура является стандартом для поиска строки, но я не уверен, что эффективный подсчет случаев будет таким же, как поиск строки.

В Python это то, что я хочу:

text_chunck = "one two three four one five six one"
occurance_count(text_chunck, "one") # gives 3.

РЕДАКТИРОВАТЬ: Кажется, Python str.count служит таким методом; однако я не могу найти, какой алгоритм он использует.

Answer 1

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

Алгоритм сопоставления строк Aho-Corasick найдет все вхождения набора строк шаблонов в целевой строке и сделает это за время O (м + n + z), где m - длина строки для поиска, n - общая длина всех сопоставляемых шаблонов, а z - общее количество найденных совпадений. Это линейный размер исходной и целевой строк, если у вас есть только одна строка для сопоставления. Он также найдет перекрывающиеся вхождения одной и той же строки. Более того, если вы хотите проверить, сколько раз набор строк появляется в некоторой исходной строке, вам нужно сделать только один вызов алгоритма. Кроме того, если набор строк, которые вы хотите найти, никогда не изменяется, вы можете выполнить O (n) как время предварительной обработки, а затем найти все совпадения в O (m + z).

Если, с другой стороны, у вас есть одна исходная строка и быстро меняющийся набор подстрок для поиска, вы можете использовать дерево суффиксов . С O (m) временем предварительной обработки строки, в которой вы будете искать, вы можете, за O (n) время на подстроку, проверить, сколько раз конкретная подстрока длины n появляется в строке.

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

Надеюсь, это поможет!

Answer 2

Бойер-Мур был бы хорошим выбором для подсчета случаев, так как он имеет некоторые накладные расходы, которые вам нужно будет сделать только один раз. Чем лучше строка шаблона, тем она лучше, поэтому для «one» это не будет хорошим выбором.

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

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

Answer 3

Hellnar, Вы можете использовать простой словарь для подсчета вхождений в строке. Алгоритм является алгоритмом подсчета, вот пример:

"""
The counting algorithm is used to count the occurences of a character
in a string. This allows you to compare anagrams and strings themselves.
ex. animal, lamina a=2,n=1,i=1,m=1
"""

def count_occurences(str):
  occurences = {}
  for char in str:
    if char in occurences:
      occurences[char] = occurences[char] + 1
    else:
      occurences[char] = 1
  return occurences

  def is_matched(s1,s2):
    matched = True
    s1_count_table = count_occurences(s1)

    for char in s2:
      if char in s1_count_table and s1_count_table[char]>0:
      s1_count_table[char] -= 1
    else:
      matched = False
      break
    return matched

  #counting.is_matched("animal","laminar")

Этот пример просто возвращает True или False, если строки совпадают. Имейте в виду, этот алгоритм подсчитывает количество раз, которое символ появляется в строке, это хорошо для анаграмм.