Publish: @shodan – indexcodecs repo

И чтобы два раза не бегать, @shodan и @IronPeter огранизовали dataset, чтобы играться с компрессией, там есть реализация в том числе и Петиной идеи в предыдущем посте.

Andrew Aksyonoff: @All
мы (Петя и я) тут сделали следующую песочницу
https://github.com/shodanium/indexcodecs
это тестовые реализации пары кодеков для полнотекстового индекса + данные для тестирования
данные == живые postings, собранные сфинксом по 150к документов википедии (можно и больше, но 2гб сырых данных вроде неплохой тестовый размер)
код == щаз два кодека, Петя сделал крутую реализацию Хаффмана, я сделал для сравнения тупой varint, собираемся по мере сил добавлять еще
собственно, кому еще интересно с этим поиграться, fork us on Github. или даже сразу в collaborators, если так удобнее
текущие планы скромные!!!
Петя может доделает спецтаблички для Хаффмана для этой коллекции, и-или прямо тулзу для их подбора
а я соотв-но может приделаю еще одну-две реализации других кодеков, типа другой реализации Varint, или Group Varint, или прочих S9/S16/PFD
ну, вот, хотим всех остальных интересующихся пригласить запрыгивать!!!

Andrew Aksyonoff: reply @Andrew Aksyonoff
о кстати какой вариант данных нашел. http://aws.amazon.com/datasets/41740
оно же http://commoncrawl.org/ – говорят 5B страниц наиндексировали
выбрать подмножество миллионов на 10-50 и по нему построить postings было бы интересно
еще интересно, десктоп e8500 оказывается на Varint быстрее сервера, а на Huffman медленнее
e8500, varint, 1.30 sec
e8500, huffman, 2.80 sec
i7-920, varint, 1.65 sec
i7-920, huffman, 2.09 sec
загадка блин

IronPeter: reply @Andrew Aksyonoff
в 32 битах небось!

Andrew Aksyonoff: reply @IronPeter
и компилятор vs2005!
а поди ж

IronPeter: reply @Andrew Aksyonoff
там Хаффман весь на ui64

Andrew Aksyonoff: reply @IronPeter
ааа…
varint наверное от частоты
на десктопе 3.17 ghz, на сервере 2.67 ghz
1.65*2666/3166 получается правда 1.39 а не 1.30!!!

Andrew Aksyonoff: reply @Andrew Aksyonoff
сделал lsb-first varint, чуть быстрее, доходит до 1.57 sec

Andrew Aksyonoff: reply @IronPeter
в этой коллекции есть такая опасность
точнее, там лексикографические title
щаз покажу
mysql> select id,title from content limit 10;
+———–+———————-+
| id | title |
+———–+———————-+
| 227512564 | Anarchism |
| 227965070 | Autism |
| 227608601 | Albedo |
| 228083555 | Abu_Dhabi_(city) |
| 226193085 | A |
| 227899793 | Alabama |
| 227096125 | Achilles |
| 227786796 | Abraham_Lincoln |
| 227941397 | Aristotle |
| 222226203 | An_American_in_Paris |
+———–+———————-+
10 rows in set (0.00 sec)
или ты про другое чо спрашивал?

IronPeter: reply @Andrew Aksyonoff
примерно про такое, да.

Andrew Aksyonoff: reply @IronPeter
ну это только заголовки, не содержимое
ну кстати что интересно, вишь документы пронумерованы с дырками, те. фокус про перенумернование может сработать

IronPeter: reply @Andrew Aksyonoff
у тебя gaps очень большие.
14 бит у меня на deltaDocId получается.
ну и очень мало когерентности между постингами.

Andrew Aksyonoff: reply @IronPeter
вот вот
btw на сервере (проц i7-920 @ 2.66 ghz) выходит вот что
huffman 21.0 compress 2.12 decompress 510mb
varint 16.5 compress 1.69 decompress 810.5mb
dummy 13.3 compress
да конечно 64бит
gcc -O3 -lstdc++ -o test test.cpp

IronPeter: reply @Andrew Aksyonoff
У меня предсказание – что Хаффмана на этой коллекции разумным кодеком не обойдешь по сжатию.
уж очень рандомно все.

Andrew Aksyonoff: reply @IronPeter
дерандомизировать и обойти!!!
но хаффмана вообще по идее должно бысть непросто.
ну посмотрим. может щаз кто-нибудь внезапно пришлет pull request с кодеком, который 200мб сделает, ыыы

IronPeter: reply @Andrew Aksyonoff
это документы надо переставлять и слова.
по локальности. А это ебатория.

Andrew Aksyonoff: reply @IronPeter
http://www2009.eprints.org/41/1/p401.pdf
aka “давайте сохраним вектор docid asc, штоп сделать помельче dgaps”
ну я могу мету собрать
у меня же при индексации влетает список docids
прямо явный, только сохранить и отсортировать
те. в этом фарше постингов его нет,
но так-то при индексации он таки есть!!!

IronPeter: reply @Andrew Aksyonoff
если кто-то на этой коллекции сделает с разумным временем препроцесса – ебок будет.

IronPeter: reply @Andrew Aksyonoff
ну да, если хотя бы http:// адреса, то плюсок уже.

Andrew Aksyonoff: reply @IronPeter
да там прямо id :)

IronPeter: reply @Andrew Aksyonoff
но только это не очень большой gain.
статистика по Хаффману примерно такая:
10.5 бит на постинг.
(14.5 бит на gap + 2.5 бит на hitNum) / 4 постинга на документ в среднем
итого 16 бит выходит.
1 бит выиграешь великой ебаторией.

Andrew Aksyonoff: reply @IronPeter
на хаффмане то наверное да
а вот на Varint всяких таки заметно должно быть
так в 2 байта dgap а так в 1 байт
сделал
810.5 мб просто varint, 753.0 мб если с перенумерацией
510.0 мб просто huffman, 462.8 мб если с перенумерацией

Это случилось на #bm25