marisa

Библиотека для создания и использования сжатых ассоциативных массивов (tries) на C++, ориентированная на эффективное хранение и быстрый поиск строковых ключей. Библиотека реализует сжатые префиксные деревья (trie) с минимальным использованием памяти и обеспечивает высокую производительность операций поиска, что делает её идеальным решением для задач автодополнения, проверки орфографии, систем ввода и других приложений, работающих с большими наборами строк.

Особенности

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

Основные компоненты

Marisa предоставляет набор классов для построения сжатых trie-структур и выполнения различных типов поиска по ним (подробнее с документацией можно ознакомиться здесь).

Построение и компиляция словаря

Библиотека позволяет построить сжатое префиксное дерево из набора строк. Процесс построения включает сортировку ключей, удаление дубликатов и оптимизацию структуры для минимизации использования памяти. Поддерживается добавление весов для ключей, что влияет на порядок поиска.

Основные классы для построения словаря:

• marisa::Keyset — контейнер для хранения ключей перед построением дерева;
• marisa::Trie — основная структура данных, представляющая сжатое префиксное дерево;
• marisa::Agent — вспомогательный класс для выполнения поисковых операций;
• Методы build() и mmap() для построения дерева и загрузки из файла.

Точный поиск и поиск по префиксу

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

Функции поиска:

• lookup() — поиск ключа по точному совпадению;
• predict() — поиск всех ключей с заданным префиксом;
• find() — поиск с использованием объекта Agent для повторного использования буферов;
• Поддержка пакетного поиска для улучшения производительности.

Приближённый поиск

Библиотека поддерживает приближённый поиск (fuzzy search), который позволяет находить ключи с небольшими отличиями от запроса. Это полезно для систем проверки орфографии и исправления опечаток.

Возможности приближённого поиска:

• Поиск с допущением одной или нескольких ошибок (расстояние Левенштейна);
• Поиск с учётом замен, вставок и удалений символов;
• Настройка порогов сходства для фильтрации результатов.

Работа с весами и приоритетный поиск

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

Функции для работы с весами:

• Присвоение весов ключам при добавлении в Keyset;
• Приоритетный поиск с возвратом ключей в порядке убывания веса;
• Методы для получения и изменения весов существующих ключей.

Итерация по ключам

Библиотека предоставляет итераторы для последовательного обхода всех ключей в дереве. Это полезно для экспорта данных, статистического анализа и других операций, требующих полного перебора.

Возможности итерации:

• Итерация по всем ключам в порядке их хранения в дереве;
• Итерация по ключам с определённым префиксом;
• Реверс-итерация для обхода в обратном порядке;
• Получение ключа по индексу.

Сохранение и загрузка

Сжатые структуры данных Marisa могут быть сохранены в файлы для последующего использования без перестроения. Формат хранения оптимизирован для быстрой загрузки и минимального использования дискового пространства.

Функции для работы с файлами:

• save() — сохранение дерева в файл;
• load() — загрузка дерева из файла;
• mmap() — отображение файла в память для нулевого копирования;
• Поддержка как бинарного, так и текстового форматов.

Использование в проекте

Документация по использованию Conan-пакетов для разработки приложений для ОС Аврора.

На сервере Conan библиотеки заранее собраны и размещены под различные версии ОС Аврора 4 и ОC Аврора 5. Для данных версий представлены архитектуры armv7hl, aarch64 и x84_64.

Библиотеку можно использовать в проекте с помощью данного conanfile.py

from conan import ConanFile

class Application(ConanFile):
    settings = "os", "compiler", "arch", "build_type"
    generators = "PkgConfigDeps"

    requires = (
        "marisa/0.2.6@aurora",
    )    

Процесс локальной сборки описан в документации.