Сериализованные справочники: работа без десериализации

[dersoverflow]

лучше сразу смотрите на Хеш-таблицу с транзакциями https://ders.by/cpp/memdb/memdb.html

1. вся хеш-таблица хранится в одном блоке памяти, т.к. вместо указателей используются смещения от начала блока.

2. таким образом, копирование всей таблицы - один вызов memcpy()! а дальше пишите в файл, передавайте по шлангу... все что угодно ;)

3. ну и, естественно, O(1) для поиска элементов. а у дерева логарифм.

[Keva]

1 и 2 справедливы для обоих подходов - и для упомянутой вами хэш-таблицы,и для сериализованного базисного дерева.

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

Хэш-таблица, демонстрирующая o(1), будет к тому же, вероятно, очень разреженной, а значит, "жирной" по размеру.

А про скорость поговорим в следующей заметке, добавим хэш-таблицу в сравнение производительности.

[dersoverflow]

построить по ней итератор, перебирающий ключи в порядке возрастания (убывания) сложно и дорого

ой ли! создаете ключ с нужным вам порядком элементов и пишете таблицу на диск.

а если надо, то и несколько разных "порядков".

будет к тому же, вероятно, очень разреженной, а значит, "жирной" по размеру

с чего бы?

назовите мне средний размер ключа/значения, и я вам скажу размер.

[Keva]

Размер ключа у полнотекстовой поисковой машины невелик: от 3-4 до 20-25 байт. В зависимости от того, словарная это лексема или неизвестная.

А как вы хотите на hash-таблице сделать итератор по ключам? Например, для реализации поиска с усечением - сло*?

[dersoverflow]

ок. пусть будет ключ 14 байт, а значения попробуем разные.

const int n=1000, ksz=14, vsz=10;
int data[50];

auto bm=new_blob_map(mp, n, false, mem_hash, mem_equal);
for (int i=0; i<n; i++) {
    data[0]=i;
    bm->insert({data, ksz}, {data, vsz});
}

out.ex_write(tx_buf(mp)+"used "+bm->info().used+"\n");

в итоге:

1. n=1000, ksz=14, vsz=10 получаем used 53808

2. n=1000, ksz=14, vsz=100 получаем used 149808

как вы хотите на hash-таблице сделать итератор по ключам?

нам же достаточно отсортированного массива слов?

значит перед записью таблицы на диск мы создаем себе ключ с отсортированным массивом "указателей" на слова. все! загружаем где угодно и сразу же пользуемся.

[Keva]

Да, разумно.

В реальности размер ключа не фиксированный, но, казалось бы, для хэш-таблицы это влияет только на её физический размер, и ограничений там быть не должно.

Типичный размер словаря ключей немного поработавшей перимущественно русскояычной полнотекстовой машины - за миллион (~60,000 русской общей лексики из активного запаса, два по столько орфографических ошибок, формально годящихся в русские слова, остальное - числа и иероглифы вроде rs232).

[BugM]

Буханка_Троллейбус.jpg

Мало данных - кладите все в мапу.

Много данных - используйте свою любимую БД. Возможно с кешем перед ней.

[Keva]

"Любимые БД" сильно просаживает производительность поисковых движков.

Требуют много памяти и медленно работают.

А я веду именно туда.

[BugM]

Вы много поисковых движков уже написали?

Или хотя бы поучаствовали в написании и эксплуатации хотя бы в течении нескольких лет в роли сеньора и выше?

[Keva]

Из больших - Апорт!, Рамблер от 2000 года и дальше, украинскую Мету.

Эти три спроектировал, в значительной мере написал, последние два потом развивал и эксплуатировал.

И несколько поменьше.

А вы?

[BugM]

В районе российского бигтеха руку приложил. И да там все мигрируется в newsql бд постепенно. Вот такие поделия как у вас выводятся. Специализированные решения на голову лучше и работают быстрее и масштабируются лучше.

В мое сообщение выше можно добавить:

Очень много данных - берите newsql.

[Keva]

Ну так какой из больших или хотя бы малых полнотекстовых движков вы сделали? Или хотя бы поучаствовали, хотя бы в качестве сеньора?

[BugM]

Держите целый доклад. Делал этот доклад не я, но не суть. Он хорошо отражает современное состояние технологий.

[Keva]

Непременно прочту.

Так всё-таки к разработке каких известных полнотекстовых поисковых движков вы имели отношение? Или хотя бы к эксплуатации?

---

Пардон, заглянул - там Apache Lucerne, разработка двадцатилетней давности, довольно громоздкая и с низким качеством поиска (отношение правильно найденных к общему количеству найденных), на сегодня - прошлый век.

Видимо, проделана большая работа над тем, чтобы оно таки шевелилось.

Терешке, думаю, тяжело пришлось обосновывать TCO.

[qw1]

Решение не production-ready, т.е. для другой структуры данных нужно будет писать новый код.
Для другой операции над данными (поиск по 2 словам, например) - тоже писать код.

Похожий подход в общем виде реализован в БД полнотекстового поиска (Sphinx, Lucene).
Там либо индексный файл, либо подход "читаю блоб 1 раз от начала до конца, для скорости прыгая через блоки, используя скип-листы). И там куча операций реализована, куча эвристик, чтобы сжать данные. Например, словарь сортируется, а соседние слова пишутся только с разницей в суффиксе.