Результат поиска в библиотеке - ошибка или особенность или моя ошибка кодирования?

Question

Я использую эту библиотеку Python, которая реализует алгоритм поиска строк Aho-Corasick, который находит набор шаблонов в данной строке за один проход. Выход не то, что я ожидаю:

In [4]: import ahocorasick
In [5]: import collections

In [6]: tree = ahocorasick.KeywordTree()

In [7]: ss = "this is the first sentence in this book the first sentence is really the most interesting the first sentence is always first"

In [8]: words = ["first sentence is", "first sentence", "the first sentence", "the first sentence is"]

In [9]: for w in words:
   ...:     tree.add(w)
   ...:

In [10]: tree.make()

In [13]: final = collections.defaultdict(int)

In [15]: for match in tree.findall(ss, allow_overlaps=True):
   ....:     final[ss[match[0]:match[1]]] += 1
   ....:

In [16]: final
{   'the first sentence': 3, 'the first sentence is': 2}

Результат, который я ожидал, был следующим:

{ 
  'the first sentence': 3,
  'the first sentence is': 2,
  'first sentence': 3,
  'first sentence is': 2
}

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

Answer 1

Я не знаю о модуле ahocorasick, но эти результаты кажутся подозрительными.Модуль acora показывает это:

import acora
import collections

ss = "this is the first sentence in this book "
     "the first sentence is really the most interesting "
     "the first sentence is always first"

words = ["first sentence is", 
         "first sentence",
         "the first sentence",
         "the first sentence is"]

tree = acora.AcoraBuilder(*words).build()

for match in tree.findall(ss):
    result[match] += 1

Результаты:

>>> result
defaultdict(<type 'int'>, 
            {'the first sentence'   : 3,
             'first sentence'       : 3,
             'first sentence is'    : 2,
             'the first sentence is': 2})

Answer 2

То, как я понимаю алгоритм Aho-Corasick и то, как я его реализовал, заставило бы меня согласиться с вашим ожидаемым результатом. Похоже, что используемая вами библиотека Python содержит ошибку или, возможно, есть флаг, по которому вы можете указать ей все совпадения, начиная с позиции, а не просто самое длинное совпадение, начинающееся с определенной позиции.

Примеры в оригинальной статье http://www.win.tue.nl/~watson/2R080/opdracht/p333-aho-corasick.pdf, подтверждают ваше понимание.