FlashText — библиотека для эффективной замены и извлечения слов из последовательностей

Познакомился недавно с библиотекой, реализованной на чистом Python, которая работает быстрее, чем regex для задач, связанных с извлечением и заменой ключевых слов в тексте. Статья рассказывает, как работает flashtext и за счет чего достигается высокая эффективность.

Как работает FlashText?

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

За счет чего так быстро?

Библиотека основана на алгоритме Ахо—Корасик и словаре на нагруженном дереве. Если в предложении N слов, то поиск займет N циклов. В этом случае время, которое потребуется для поиска, зависит только от количества слов в предложении. И шаг, который проверяет, находится ли нужное слово в базе ключевых слов, быстро выполнится за счет операции поиска в словаре. Если использовать regex, то количество циклов будет зависеть от количества слов в базе ключевых слов. Получается, если исходная строка «сколько стоит Namecoin», а набор ключевых слов {'Gridcoin', 'Peercoin', 'Namecoin', 'SwiftCoin', 'Omni'}, то в случае с FlashText будет 3 цикла, а с regex — 5. И если количество ключевых слов значительное (скажем, от 500), разница будет огромной. Так, Radim Řehůřek сообщает, что ему удалось добиться 28-кратного ускорения при следующих исходных данных: 1 тыс. ключевых слов и около 10 000 токенов на документ.

Примеры использования

Замена:

from flashtext.keyword import KeywordProcessor

keyword_processor = KeywordProcessor()
keyword_processor.add_keyword('SwiftCoin', 'Namecoin')

new_sentence = keyword_processor.replace_keywords('сколько стоит SwiftCoin')
print(new_sentence)
# сколько стоит Namecoin

Поиск:

from flashtext.keyword import KeywordProcessor

keyword_processor = KeywordProcessor()
keyword_processor.add_keyword('SwiftCoin')

keywords_found = keyword_processor.extract_keywords('сколько стоит SwiftCoin')
print(keywords_found)
# ['SwiftCoin']

Больше примеров — в документации.