Доступное для поиска статическое строковое хранилище

Question

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

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

Я экспериментировал с Tries для создания индекса с возможностью быстрого поиска по именам, но в настоящее время он дополняет хранение строковых данных каждого объекта.

Эти данные являются статическими и распространяются в виде отдельного двоичного файла вместе с приложением.

Answer 1

У меня ранее был некоторый успех со смесью сжатия LZW с большой таблицей, а затем интернирования до 32-битных идентификаторов. Для достаточно похожего корпуса LZW может сжиматься до 32 бит, поэтому для идентификатора есть флаг, поэтому он обрабатывается как сжатый битовый шаблон, а не как ключ в хеш-таблице. Поскольку LZW основан на префиксах, вы можете искать его несколько похожим способом на три, но это немного сложнее; проще сделать тест, основанный на том, содержит ли битовый шаблон какой-либо из символов запроса при расширении, и если это так, разверните строку и используйте обычное сравнение строк.