Skip to content

Latest commit

 

History

History
69 lines (53 loc) · 3.32 KB

README_ru.md

File metadata and controls

69 lines (53 loc) · 3.32 KB

English

Dictionary

Ищет входждения подстроки в заданном словаре

Зависит от Qt. Можно собрать с Qt5 или Qt6.

Сборка

Необходим CMake версии 3.17

Выполнить в корне репозитория:

mkdir build
cd build

затем сгенерировать проект с помощью комманды

cmake ..

Можно дополнительно указать -DUSE_QT6=ON если хотите собрать проект с Qt6 вместо Qt5.
В некоторых случаях нужно явно указать -DUSE_QT6=OFF (например если кэш CMake уже был с генерирован с -DUSE_QT6=ON)
Также возможно потребуется устоновить переменную CMAKE_PREFIX_PATH.
-DCMAKE_PREFIX_PATH="path/to/Qt/lib/cmake" или
-DCMAKE_PREFIX_PATH=/usr/include/{host}/qt{version}/ на Ubuntu.

Выполните, чтобы собрать проект:

cmake --build . --config Release

Запуск приложениея

Чтобы запустить программу выполните команду:

./Dictionary [--dont-store] [dictionary file]

Если указан аргумент --dont-store приложение не хранит словарь в памяти и каждый раз читает его с диска.
Если dictionary file не указан, программа попытается открыть файл ./words.txt.
Порядок аргументов важен.
Этот файл был использован в тестах.

Протестировано

  • на Windows 10, MSVC 2019, с Qt 5.15.2 и Qt 6.0.3
  • на Ubuntu 20.04, g++ 9.3.0, с Qt 6.0.3
    • с Qt 5, для Qt установленной с помощью apt

Алгоритмы поиска

Программа использует упрощённую версию алгоритма быстрого поиска для определения подстроки.

m - размер подстороки (needle), n - размер строки (haystack), s - размер алфавита.

  • Алгоритм требует препроцессинг, с временной сложнностью O(m + s). препроцессинг нужно исполнить для каждого needle.
  • Временная сложность самого алгоритма - O(mn).

s = 2^8 = 256.

Алгоритм имеет несколько упрощений:

  • Поиск запускается для одной строки, а не всего текста
  • Когда одно вхождение найдено, поиск останавливается

В коде: препроцессинг - Dictionary::quickSearchPreprocessing, поиск - Dictionary::quickSearchImplementation

Посик последовательных символов (необязательно)

Этот алгоритм не требует препроцессинга и обладает временной сложностью O(n)

В коде: поиск - Dictionary::sequenceSearchImplementation