нужно сделать поисковый индекс
чтобы можно был найти "cde" в "abcdefgh" без тупого перебора
по идее это решается вектроризацией которая в ИИ применяется
но как точно это сделать не знаю
потому что если букву просто будут комопнентами ветора, то abd будет ближе к abc, чем ab
Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не более года. (с) Эксперт, авторитет и профессионал из 1957 г.
Ну как вариант, сразу приходит в голову использовать битовые маски и SIMD-овыми операциями искать вхождения. Причем битовая маска подготовлена со сдвигом искомой строки, ну типа:
0: cde
1: cde
2: cde
3: cde
4: cde
...
И такую штуку прикладываем, проверяя за раз N символов, потом смещаемся на N и ищем вхождение во втором куске. Для AVX512 N будет 512, что теоретически ускорит +- в 500 раз.
Здравствуйте, Pzz, Вы писали:
Pzz>Непонятно. Ты ищешь подстроку в конкретной строке, или у тебя миллион строк, и ты хочешь быстренько выбрать те, которые содержат указанную подстроку?
второй
Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не более года. (с) Эксперт, авторитет и профессионал из 1957 г.
Здравствуйте, sergii.p, Вы писали:
SP>Здравствуйте, Barbar1an, Вы писали:
B>>по идее это решается векторизацией которая в ИИ применяется
SP>поищи по word2vec. Там большое количество библиотек готовых: gensym, spacy, fasttext, sentence-transformers и др
наверно мне эти либы не очень подойдут, потому что в них расстояние семантическое вычисляется, а нужно так сказать орфографическое
Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не более года. (с) Эксперт, авторитет и профессионал из 1957 г.
Здравствуйте, Barbar1an, Вы писали:
B>нужно сделать поисковый индекс
Индекc для чего. Для полнотекстового поиска, для поиска похожих.
B>чтобы можно был найти "cde" в "abcdefgh" без тупого перебора
Обычный полнотекстовый индекс.
B>по идее это решается вектроризацией которая в ИИ применяется
ага точно, еще можно блокчеин прикрутить.
B>потому что если букву просто будут комопнентами ветора, то abd будет ближе к abc, чем ab
Для такого вводят функцию растояния и разбивают на кластеры и строят kd,vp,r,m деревья.
Здравствуйте, kov_serg, Вы писали:
_>Здравствуйте, Barbar1an, Вы писали:
B>>нужно сделать поисковый индекс _>Индекc для чего. Для полнотекстового поиска, для поиска похожих.
B>>чтобы можно был найти "cde" в "abcdefgh" без тупого перебора _>Обычный полнотекстовый индекс.
B>>по идее это решается вектроризацией которая в ИИ применяется _>ага точно, еще можно блокчеин прикрутить.
B>>потому что если букву просто будут комопнентами ветора, то abd будет ближе к abc, чем ab _>Для такого вводят функцию растояния и разбивают на кластеры и строят kd,vp,r,m деревья.
злой ты какойто, но спасибо)
(а блокчейн я уже прикрутил, точнее оно на блокчейне и нужно)
Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не более года. (с) Эксперт, авторитет и профессионал из 1957 г.
Здравствуйте, Barbar1an, Вы писали:
B>нужно сделать поисковый индекс B>чтобы можно был найти "cde" в "abcdefgh" без тупого перебора B>по идее это решается вектроризацией которая в ИИ применяется B>но как точно это сделать не знаю B>потому что если букву просто будут комопнентами ветора, то abd будет ближе к abc, чем ab
В ИИ там семантическое расстояние, можно ChromaDB взять. Но тебе же другое нужно?
По идее, если строк много и они не очень длинные, то можно построить индекс типа trigram, ну или взять уже готовое решение типа lucene.
Если строки по которым ищешь длинные, то можно посмотреть в сторону суффиксных деревьев.
Re[2]: Векторизация слов для быстрого поиска похожих
Здравствуйте, MaximVK, Вы писали:
MVK>Здравствуйте, Barbar1an, Вы писали:
B>>нужно сделать поисковый индекс B>>чтобы можно был найти "cde" в "abcdefgh" без тупого перебора B>>по идее это решается вектроризацией которая в ИИ применяется B>>но как точно это сделать не знаю B>>потому что если букву просто будут комопнентами ветора, то abd будет ближе к abc, чем ab
MVK>В ИИ там семантическое расстояние, можно ChromaDB взять. Но тебе же другое нужно? MVK>По идее, если строк много и они не очень длинные, то можно построить индекс типа trigram, ну или взять уже готовое решение типа lucene. MVK>Если строки по которым ищешь длинные, то можно посмотреть в сторону суффиксных деревьев.
да, я уже понял что мне нужно не семантичское, а расстояние Левенштейна
Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не более года. (с) Эксперт, авторитет и профессионал из 1957 г.
Re[3]: Векторизация слов для быстрого поиска похожих
Здравствуйте, Barbar1an, Вы писали:
B>да, я уже понял что мне нужно не семантичское, а расстояние Левенштейна
Хм, а вот тут я не понял
Тебе же нужно подстроку найти?
А расстояние Левенштейна — это синтаксическая близость слов, считается как количество замен/вставок/удалений букв которые надо сделать в одном слове, чтобы получить другое.
Здравствуйте, Barbar1an, Вы писали:
B>нужно сделать поисковый индекс B>чтобы можно был найти "cde" в "abcdefgh" без тупого перебора
Подумалось про частный "дешёвый" случай.
Про вариант использовать т.н. n-граммы тебе уже написали.
Если расмотреть пример частного сценария, когда тебе надо искать ТОЛЬКО последовательность фиксированного размеера (3,4,5...) символов, то реализовать это можно малой "кровью":
-создаёшь список n-gram для т.н. слов, т.е. разбиваешь слово на n-граммы (плавающее окно символов, напр разбиение на tri-gram'ы (по три символа) для abcd: abc bcd cd ,)
-и связь many-to-many между словами и n-граммами
Для реализации можно использовать хоть реляционную DB, хоть какую-нибудь key-value базу.
Re[2]: Векторизация слов для быстрого поиска похожих
Здравствуйте, kov_serg, Вы писали:
_>Для такого вводят функцию растояния и разбивают на кластеры и строят kd,vp,r,m деревья.
а какое из этих деревьев лучше если стоится оно последовательно? т.е. вначале у нас только 1 элемент известен, а не какоето множество
Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не более года. (с) Эксперт, авторитет и профессионал из 1957 г.
Re[3]: Векторизация слов для быстрого поиска похожих
Здравствуйте, Barbar1an, Вы писали:
B>а какое из этих деревьев лучше если стоится оно последовательно? т.е. вначале у нас только 1 элемент известен, а не какоето множество
Самое простое r дерево, там всё плоскотями делется, в vp сферам. Но для 1 элемента это слегка бесполезно
А так выбираете направление и в доль него кластеризуете, разбиваете по кластерам. Потом в каждом кластере делаете тоже самое.
Re[4]: Векторизация слов для быстрого поиска похожих
Здравствуйте, kov_serg, Вы писали:
_>Здравствуйте, Barbar1an, Вы писали:
B>>а какое из этих деревьев лучше если стоится оно последовательно? т.е. вначале у нас только 1 элемент известен, а не какоето множество _>Самое простое r дерево, там всё плоскотями делется, в vp сферам. Но для 1 элемента это слегка бесполезно _>А так выбираете направление и в доль него кластеризуете, разбиваете по кластерам. Потом в каждом кластере делаете тоже самое.
r не годится там есть минимум вершин, оно тоже из 1 элемента не стоится
Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не более года. (с) Эксперт, авторитет и профессионал из 1957 г.
Здравствуйте, kov_serg, Вы писали:
_>Самое простое r дерево, там всё плоскотями делется, в vp сферам. Но для 1 элемента это слегка бесполезно _>А так выбираете направление и в доль него кластеризуете, разбиваете по кластерам. Потом в каждом кластере делаете тоже самое.
Я думаю нужно какой-то алгортм дерева типа следущщего (вроде это M-дерево)
делаем корень
дальше напихиваем все новые точки в его payload
как только точек стало слишком много, делим их на N подпространств по какомуто критерию скучкованности
но тут вопрос:
будем делить так чтобы все остальные новые точки попадали в эти N подпространств, (кароче плоскостями делить)
либо
все полученные подпространства не будут заполнять всё пространство (например орагничиваться своим радиусом) и значит у корня могут быть еще дети
пока не понял как лучше
Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не более года. (с) Эксперт, авторитет и профессионал из 1957 г.
