/suffix_tree

Primary LanguagePython

Приложение ищет слова из словаря, в которых есть заданная подстрока

Установка и запуск

Вы можете использовать виртуальное окружение, если хотите изолировать библиотеки, используемые в приложении от системных.

  1. Установите нужные библиотеки: python -m pip install -r requirements.txt
  2. Запустите приложение: python searcher.py

Работа приложения

При запуске показывается окно для ввода текста и список результатов. Для выхода нужно нажать Ctrl-C.

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

Результаты можно прокручивать мышью.

Попробуйте ввести test, чтобы увидеть, как это работает.

Структура приложения

Приложение состоит из двух файлов: searcher.py, отвечающий за само отображение, и sset.py, в котором находится структура данных для поиска по строкам.

В файле searcher.py вы можете менять только константу FILENAME

Файл sset.py вы можете менять как угодно, но сигнатуры методов класса SSet должны остаться неизменными:

  1. Конструктор __init__(self, filename) принимает имя файла, в котором находится словарь.
  2. Метод load(self) загружает все слова из словаря. Предполагается, что в словаря каждая строка содержит одно слово. Словарь не обязательно отсортирован в алфавитном порядке.
  3. Метод search(self, substring) возвращает все слова из словаря, которые содержат заданную подстроку substring.

Задача

Сейчас структура SSet просто хранит список всех слов и ищет подстроки в каждом слове каждый раз. Кроме того, в реализации есть ошибка и добавляется лишнее слово some wrong word!.

Реализовать структуру данных SSet корректно и эффективно.

Для этого реализуйте суффиксное дерево. Если строка содержит подстроку, то подстрока будет префиксом какого-либо суффикса.

Проверка

Файл small-words.txt содержит 15920 пятибуквенных слов и используется с неэффективной структурой.

Файл words.txt из 370105 слов нужно использовать для проверки эффективной структуры.

Критерии оценки:

  • программа выдаёт суффиксы, которые действительно есть в тексте; программа не выдаёт суффиксов, которых в тексте нет;
  • программа использует суффиксное дерево;
  • нет заметного лага при использовании на словаре words.txt при поиске подстрок длиной более трёх символов.