Какой наиболее производительный поиск по JSON объектам на момент 2020?

Question

[Kizzeon]

У меня есть достаточно большой файл с JSON данными (150 тысяч json-объектов - в сумме ~50 мегабайт) и мне нужно быстро проводить по ним поиск (в < 150 мс), сортируя варианты с наибольшим количеством совпадающих с N текстом символов. Всего должно выводиться 10 найденных объектов.

В JSON также есть кастомные символы (иероглифы и прочие символы).

Структура Json выглядит следующим образом:

{"item": 643, "name": "Уникальное название товара `кастомный символ здесь`", "type": "Кастомный символ"}

У каждого объекта одни и те же свойства (item, name, type...) и отличаются только их значения.

Какие производительные варианты поиска по обычным(английским/русским) и кастомным (например, китайские иероглифы) символам в JSON вы посоветуете?

Comments

[Dima Polos]

У Вас JSON-база хранится в файле и Вы с него читаете данные?

[Dima Polos]

Для JSON есть NoSQL базы, например MongoDB, там все поиски и сортировка оптимизированы.

[Kizzeon]

Dima Polos, Поиск необходим в Оффлайн, оттого и бд отсекаю

[hzzzzl]

Kizzeon, а если sqlite локальный?
на худой конец встроенный в хром indexedDB

[Everything_is_not_so_bad]

Есть на Go пакет для очень эффективного извлечения данных из JSON: https://github.com/tidwall/gjson
Может, для JS тоже что-нибудь похожее есть.
Извлекая данные, построить индекс и по нему искать.

Answer 1

[ThunderCat]

Классикой поиска в больших файлах является Sphinx, однако у вас не набор букв, а структурированные данные, по этому я думаю вам будет логичней создать параметризованную модель и перенести все в бд, хотя бы в SQLite (вроде у вас достаточно простая модель данных). Но тут тоже есть нюансы, ну и возможно это вам просто не подходит по ряду причин. Тогда сфинкс для вас лучший вариант, хотя 50 мб файл как-то мелковато, обычно сфинкс ставят для работы с гигабайтными файлами, но будет "на вырост".

Comments

[Kizzeon]

Мне вполне подходит SQLite, но теряюсь в догадках - какую библиотеку/npm использовать для этого?

[ThunderCat]

Kizzeon, https://www.google.com/search?q=sqlite+nodejs+api

Answer 2

[Dimonchik]

чЮдесов нет

все быстрые поиски - это пресозданные индексы
явно или неявно

в вашем случае - если речь о фронте - все упирается в парсер JSON

в Питоне самый быстрый ujson, обвязка над С, в Go - тоже пару вариантов
в JS вряд ли что-то будет быстрее нативного

но вот с локальной базой, хотя бы levelDB все уже повеселее

Comments

[Kizzeon]

До этого использовал FlexSearch - очень быстрый поисковик по json
Но на кастомных символах он становится сильно медленным

[Kizzeon]

И в гитхабе levelDB

There is no client-server support builtin to the library. An application that needs such support will have to wrap their own server around the library.

Answer 3

[xmoonlight]

Указатель нужен (в книгах был, в конце).
Из него делаем "дерево": А, Б, В, ....АА, АБ, АВ,..., и с каждого потом: АБА, АББ,.... и т.д. по всем "цепочкам" букв, встречающихся в словах указателя.

При поиске - делаем спуск по "дереву" для каждого слова.
Чем больше слов поискового запроса попало на одну запись, тем она релевантнее запросу.
Это будет точно менее 150мс.

Comments

[Kizzeon]

Немного не понял подход =(

Но спасибо, поищу реализации

Answer 4

[profesor08]

Ну можно отсечь парсинг самого JSON, создание объектов и тд, а работать как со строкой. Составить регулярку, которая будет возвращать нужные куски строки, а потом уже переводишь их в объекты. Можешь отсортировать если хочешь. По поводу производительности ничего не могу сказать, надо проверять.

Comments

[Kizzeon]

Regex пробовал и он сильно медленнее. Вплоть до 800-1200 мс на поиск и сортировку

[profesor08]

Kizzeon, значит JSON.parse и работай как с массивом

Answer 5

[hzzzzl]

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

Answer 6

[Alex]

Неавно решал подобную задачу, тестовое задание. Как и говорят, ребята выше, без дополнительных индексов быстро не получится. В моем случае поиск был всего по двум полям, поетому я пересоздас себе масив по этим ключам и искал, этого было достаточно. В процесе разбора наткнулся на такой вот пакет https://www.npmjs.com/package/json-index есть и аналоги, может помочь. Но лично я не пробовал.