Здравствуйте, vdimas, Вы писали:
V>У меня есть решение, но мне банально интересно, к какой сложности относятся подобные задачи? ))
Сопоставить каждому слову свой вектор в N-мерном пространстве, найти в нем K ближайших за логарифм. И уже с ними линейно сравниться алгоритмом типа Левенштейна.
Найти в пространстве — можно взять готовую библиотеку типа faiss или любой аналог.
Как сопоставить слову вектор — вот тут я бы взял лёгкую нейросеть для текстовых эмбеддингов. Твое требование без ИИ тут не канает, потому что это не ИИ, хоть и нейросеть.
Здравствуйте, Nuzhny, Вы писали:
N>Как сопоставить слову вектор — вот тут я бы взял лёгкую нейросеть для текстовых эмбеддингов.
Да, вот тут единственно, что плохо понятно в твоём предложении.
Обычно длина "ключевых слов" небольшая (8 символов в среднем), плюс алфавит небольшой — 26 английских букв + 33 русских + 10 цифр плюс некие символы +-*/"(){}, которые все можно закодировать одним символом (раз всё равно потом на найденный список натравливаем Левенштейна), ну и сопоставить английские символы русским и сами русские символы ужать (и-й, е-ё), т.е. можно сделать преобразованный алфавит меньше 32 символов, это 5 бит на символ, т.е. средняя строка влезет в байтовое представление двух int32.
Моё предложенное решение такое:
Построить граф ДКА разбора всех "ключевых" слов. Граф состояний сделать однонаправленным, без циклов, т.е. будет дерево разбора.
Точное соответствие будет найдено за O(N), где N — длина строки.
Для нечёткого соответствия можно протягивать по этому дереву НКА, т.е. множить кол-во вариантов на каждом шаге, с накоплением количества отличий (разницы).
Алгоритм Левенштейна допускает любые опечатки плюс перестановки, т.е. коэфициент размножения кол-ва НКА-состояний на каждом шаге будет 32*2 (сколько символов в алфавите), в конечных состояниях будет список всех слов, которые при преобразовании алфавита дали нам текущую строку разбора — уже сильное ограничение.
При накоплении расстояния/ошибок на каждом шаге большинство НКА будет отваливаться если сделать как принято на практике максимальное расстояние 2. Т.е, грубо, оценка кол-ва протягиваемых НКА на каждом шаге будет 32*32.
Поэтому, есть еще идея допускать не произвольные опечатки, а только самые популярные, например, C-S, X-KS, U-Y, а так же соседние символы на обычной и мобильной клавиатуре (тоже источник опечаток). Т.е. коэф. размножения состояний НКА будет на порядок меньше 10*10.
Из готовых я видел нечеткое сравнение по индексу в библиотеке Lucene (есть джавовская и дотнетная версия), но там такие тормоза, что приплызд.
Поэтому, есть идея искать символ в 3 этапа:
Первый раз прогнать по дереву разбора ДКА-автомат (это даже быстрее, чем поиск по хеш-таблице) — будет найдено или нет точное соответствие.
Затем запуск описанного алгоритма с протягиванием НКА, а затем уже запуск полного нечеткого сравнения из Lucene, если "быстрый" алгоритм не нашёл соответствия.
Если рассуждать дальше, "быстрый" алгоритм можно ограничить, например, одной опечаткой и одной перестановкой, что даст совсем небольшое кол-во одновременно протягиваемых состояний НКА (примерно десяток), т.е. почти мгновенную его работу.
Итого, для полного соответствия будет мгновенный ответ, для 1-й ошибки — почти мгновенный, для более одной ошибки — медленнее всего.
Здравствуйте, vdimas, Вы писали: F3V>>Уточнённая грамматика V>Занятный инструмент. V>Без стёба. ))
Так или иначе получился очень интересный результат:
алгоритм + реализация (ИИ немного посоветовал преобразования): V>Вот бы нагенерить хотя бы пол-миллиона ключевых слов из алфавита и натравить на разбор десятков различных предложений, где встречаются ключевые слова.
Получился синтетический тест по алфавиту из строчных русских букв.
Запускались тесты для 1000 и 100000 брендов и с 2 внесёнными опечатками.
Генерировались слова по 3,4,5,6,7,8 символов группами с добавлением к старым.
После добавления каждой группы, брались её первые 1000 уникальных слов и проверялись на совпадения.
V>В этой предметной области, смотрю, сравнивают различные алгоритмы/реализации по времени нечеткого поиска 1000 запросов в словаре из полумиллиона ключевых слов. V>(т.е. десяток примеров надо будет прогнать в цикле 100 раз).
Можно на основе синтетического теста прикинуть. V>(Если PEG-парсер покажет хоть сколько-нибудь интересные результаты, то можно будет попробовать переписать сгенерированный код на компилируемом языке, например на плюсах, и опять проверить)
Тут сам парсер почти не важен, только код на JavaScript задействован.
PEG-парсер понадобился лишь для удобства и интерактивной настройки и тестирования.
Здравствуйте, Janus, Вы писали:
V>>Допустим, у нас есть алгоритмы поиска расстояния м/у словами. V>>А как быстро производить нечёткое сравнение в словаре из миллиона слов? J>Это можно решить на уровне БД
По ссылке:
Как проиндексировать функцию Левенштейна я не придумал
Здравствуйте, vdimas, Вы писали:
V>Есть входная строка, например "планшет Samsung" V>Затем даётся дополнительное ТЗ — необходимо сделать поиск нечётким, т.е. с возможными опечатками. V>У меня есть решение, но мне банально интересно, к какой сложности относятся подобные задачи? ))
Есть набор из названий брендов (озвучено — порядка миллиона).
Есть входная строка, например "планшет Samsung"
Необходимо без ИИ сопоставить бренд из словаря этой строке.
Задача выглядит простой для решения — произвести токенизацию строки и затем поиск в хеш-таблице, где хранятся бренды.
Затем даётся дополнительное ТЗ — необходимо сделать поиск нечётким, т.е. с возможными опечатками.
И сделать поиск эффективным, т.е. придумать такой алгоритм, который не стал бы последовательно перебирать все слова используя, допустим, стороннюю библиотеку поиска дистанции между словами (есть полно готовых таких алгоритмов).
У меня есть решение, но мне банально интересно, к какой сложности относятся подобные задачи? ))
Здравствуйте, bnk, Вы писали:
bnk>- (рекомендуемый вариант) алгоритм SymSpell как "наиболее популярный и эффективный для этой задачи", O(1)
Да, у меня сразу же была наивная идея сгенерить всевозможные варианты ошибок, но там резкий комбинаторный взрыв получался.
SymSpell использует только удаления, что ограничивает конечное множество.
Плюс, эти удаления, порождают в общем случае перекрывающиеся варианты, что уменьшает кол-во уникальных вариантов (в отображении надо будет хранить 1 и более результатов)
Но в целом — оч неплохой подход, если много памяти. ))
=====
Единственно что — 2 удаления симметрично не равны расстоянию слов 2, если есть опечатки-вставки до 2-х лишних символов.
Т.е., входные токены надо будет искать последовательно для 2-х удалений, 3-х удалений и 4-х удалений, что уже жопа получается. ))
Тогда придётся ограничить кол-во лишних вставок 1.
Здравствуйте, vdimas, Вы писали: V>Есть набор из названий брендов (озвучено — порядка миллиона). V>Есть входная строка, например "планшет Samsung" V>Необходимо без ИИ сопоставить бренд из словаря этой строке. V>Затем даётся дополнительное ТЗ — необходимо сделать поиск нечётким, т.е. с возможными опечатками.
Почему только эти? Тупо промахнулся на клавиатуре по соседней кнопке (любая буква), или буквы местами перестаивались (у меня часто так) — да полно вариантов опечаток
Здравствуйте, Hоmunculus, Вы писали:
F3V>>Возможные опечатки: u->a | a->u | u->y | y->u
H>Почему только эти? Тупо промахнулся на клавиатуре по соседней кнопке (любая буква), или буквы местами перестаивались (у меня часто так) — да полно вариантов опечаток
Потому что это пруф оф концепт, Minimum Viable Product (минимально жизнеспособный продукт).
Если хотите боевой пример себе сделать, то:
F3V>Нужно подготовить два словаря: брендов и опечаток.
Здравствуйте, vdimas, Вы писали:
V>Такая задача.
V>Есть набор из названий брендов (озвучено — порядка миллиона). V>Есть входная строка, например "планшет Samsung"
V>Необходимо без ИИ сопоставить бренд из словаря этой строке. V>Задача выглядит простой для решения — произвести токенизацию строки и затем поиск в хеш-таблице, где хранятся бренды.
V>Затем даётся дополнительное ТЗ — необходимо сделать поиск нечётким, т.е. с возможными опечатками.
V>И сделать поиск эффективным, т.е. придумать такой алгоритм, который не стал бы последовательно перебирать все слова используя, допустим, стороннюю библиотеку поиска дистанции между словами (есть полно готовых таких алгоритмов).
V>У меня есть решение, но мне банально интересно, к какой сложности относятся подобные задачи? ))
Во-первых, отмечу, что решение точным быть не может. "Победа" и "Обеда" могут быть всегда признаны одинаковыми. А может, и "Беда" сюда же.
Далее в предположении, что имена брендов содержат только латинские буквы. Если это не так — нужно больше битов.
Сопоставляем каждому имени бренда 32-битное число BB, в котором каждый бит указывает на наличие соответствующей буквы алфавита (бит0 — есть буква a, бит1 — есть буква b и т.д.). Если в имени бренда некоторая буква встречается >1 раза, просто игнорируем этот факт. Это можно сделать заранее. А также для каждого имени бренда определяем длину слова BL
Для кандидата выполняем те же действия, получив аналогичное число CB и длину CL
Если разница длин BL и CL больше некоторого порога PL — отвергаем кандидата. Слишком большое различие длин.
int D = CB & BB;
Если в D единичных битов меньше некоторого порога (зависящего от длины слова, тут надо подумать), имя B[i] отвергается. Слишком большое различие набора букв.
Для оставшихся B[i] проводим сравнение всерьез — по Левенштейну, скажем.
Здравствуйте, F3V, Вы писали:
F3V>Нужно подготовить два словаря: брендов и опечаток.
На слово-название бренда длиной 8 символов получается более 350 тыс вариантов с опечатками до 2 шт.
F3V>Миллион для таких словарей не много, должно потянуть.
Из миллиона слов получится 350 миллиардов вариантов.
Пусть даже часть опечаток от разных ключевых слов склеятся в один, это не спасёт. ))
Некоторые алгоритмы предлагают подход от обратного — генерить всевозможные опечатки не словаря, а входного токена.
Т.е., алгоритм такой:
— проверили точное соответствие;
— если не нашли, то нагенерили все варианты с одной опечаткой (это замена одной буквы=N*K, где K — размер алфавита, плюс все соседние перестановки=N, плюс все удаления по одному символу=N, т.е. разветвление получается примерно N(K+2) на каждую ошибюку), проверили в цикле все нагенерённые варианты;
— если не нашли, нагенерили из каждого варианта еще варианты, в этом месте и получается более 350 тыс уже при допущении 2-х ошибок.
Далее считается, что 3 ошибки на практике встречаются редко (это уже более 200 млн вариантов от исходного слова) и их лучше не обрабатывать.
Поэтому, в таких системах живёт магическое число 2.
Однако, в реальных системах проверки правописания всё чуть проще, т.к. алфавит намного уже. А названия брендов могут состоять, к примеру, из русских и латинских букв, плюс цифры, плюс различные знаки !-+* и т.д. Т.е. алфавит в разы больше, разветвление на каждой ошибке слишком большое.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Сопоставляем каждому имени бренда 32-битное число BB, в котором каждый бит указывает на наличие соответствующей буквы алфавита (бит0 — есть буква a, бит1 — есть буква b и т.д.). Если в имени бренда некоторая буква встречается >1 раза, просто игнорируем этот факт. Это можно сделать заранее. А также для каждого имени бренда определяем длину слова BL PD>Для кандидата выполняем те же действия, получив аналогичное число CB и длину CL
Я тоже думал о различных вариантах приближённого кодирования, но оно не давало ничего в терминах сложности O.
Более того, перекодированные варианты неудобны при нахождении ближайших.
Например, у обычных чисел мы можем найти ближайших соседей двоичным поиском в отсортированном массиве.
А если все биты равноправны, что тогда делать? ))
Есть вариант автомата Ливенштейна.
Я тоже за считанные минуты пришёл к похожему решению.
В терминах сложности получается похожее решение, но у него есть предварительное кодирование. https://habr.com/ru/articles/275937/
Реализация существует на Джава и C#, реализация ужасна — я бы пристрелил. ))
Но там это объяснимо, т.к. эта система парсит и строит автоматы на лету, т.е. на вход подаются выражения навроде "find Samsong~" (специально написал с опечаткой).
Тильда означает нечеткий поиск в индексе.
А так-то для конкретной выделенной задачи можно сделать всё плоско в памяти, резко её сэкономив и улучшив быстродействие в разы.
F3V>>Нужно подготовить два словаря: брендов и опечаток.
V>На слово-название бренда длиной 8 символов получается более 350 тыс вариантов с опечатками до 2 шт.
наиболее реально составить список наиболее вероятных опечаток и прогонять их через regex.
Здравствуйте, pik, Вы писали:
pik>наиболее реально составить список наиболее вероятных опечаток и прогонять их через regex.
Да, эта же идея пришла мне в голову первой.
Но только не regex, а предварительно составленное дерево разбора.
Причём, в тщательно выбранном представлении в памяти (обычно это два плоских массива, хранящих смещения — массив состояний и массив переходов, везде только числа, без указателей/ссылок)
И не заранее составить список всех самых вероятных опечаток (там всё равно получается приличный комбинаторный взрыв вариантов, память слишком отожрет), а прогонять одновременно варианты с дистанцией до 2-х ошибок, т.е. выстраивать эти варианты динамически. Ну или же перебирать эти варианты у исходного слова и сравнивать со словарём все эти варианты поочерёдно — суть та же, но другая реализация. Тут только сравнительное тестирование покажет. ))
Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, bnk, Вы писали:
bnk>>- (рекомендуемый вариант) алгоритм SymSpell как "наиболее популярный и эффективный для этой задачи", O(1)
V>Да, у меня сразу же была наивная идея сгенерить всевозможные варианты ошибок, но там резкий комбинаторный взрыв получался. V>SymSpell использует только удаления, что ограничивает конечное множество. V>Плюс, эти удаления, порождают в общем случае перекрывающиеся варианты, что уменьшает кол-во уникальных вариантов (в отображении надо будет хранить 1 и более результатов)
Насколько я понял там формально доказано что удаления эквивалентны опечаткам, поэтому это и работает
Здравствуйте, vdimas, Вы писали: V>Из миллиона слов получится 350 миллиардов вариантов. V>Пусть даже часть опечаток от разных ключевых слов склеятся в один, это не спасёт. ))
Да. Вспомнил, действительно так и было На парадигме русского языка память всю тратил.
Там разбиение на суффиксы и окончания и их объединение уменьшило эту проблему для слов русского языка. V>Некоторые алгоритмы предлагают подход от обратного — генерить всевозможные опечатки не словаря, а входного токена.
Тогда хранение слов может быть не словарным, что не даст возможности итерироваться по словарю, но это не всегда нужно. V>Т.е., алгоритм такой: V>- проверили точное соответствие; V>- если не нашли, то нагенерили все варианты с одной опечаткой (это замена одной буквы=N*K, где K — размер алфавита, плюс все соседние перестановки=N, плюс все удаления по одному символу=N, т.е. разветвление получается примерно N(K+2) на каждую ошибюку), проверили в цикле все нагенерённые варианты; V>- если не нашли, нагенерили из каждого варианта еще варианты, в этом месте и получается более 350 тыс уже при допущении 2-х ошибок.
Этот алгоритм предполагает поиск единственного совпадения, возможно лучшего, но их может быть несколько вариантов одновременно.
По идее, количество вероятных ошибок должно зависеть от длины слова, но пусть будет пока две. V>Далее считается, что 3 ошибки на практике встречаются редко (это уже более 200 млн вариантов от исходного слова) и их лучше не обрабатывать.
В языке есть морфологические правила. Но с брендами такое вряд ли пройдёт. V>Однако, в реальных системах проверки правописания всё чуть проще, т.к. алфавит намного уже. А названия брендов могут состоять, к примеру, из русских и латинских букв, плюс цифры, плюс различные знаки !-+* и т.д. Т.е. алфавит в разы больше, разветвление на каждой ошибке слишком большое.
Уточнённая грамматика.
/*
=== НАСТРОЙКИ ===
Добавляем в словарь так:
названии Название-с-символами,samsung, nokia .
Добавляем возможные опечатки так:
опечатки a -> o, u -> a, 0123 -> 4567, аб -> цд .
=== ФАЙЛ РАЗБОРА ===
названия "Метро",Домик-в-деревне,samsung,sunsung,nokia,microsoft,1984.
опечатки
abcdefghijklmnopqrstuvwxyz ->
abcdefghijklmnopqrstuvwxyz,
абвгдеёжзийклмнопрстуфхцчшщъыьэюя ->
абвгдеёжзийклмнопрстуфхцчшщъыьэюя,
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ ->
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ,
012345689 -> 012345689.
"Митра" Бобик-в-деревне Домик-в-деревне
sunsung samsung sumsung samsyng sumsyng sumcung
nakia nakua macrosoft microsoft 1945
*/
{
if (!options.бренды) { options.бренды = {}; }
if (!options.опечатки) { options.опечатки = {}; }
options.addHash = (dictionary, text)=>{
let hash = dictionary[options.hash(text)];
if (!hash) {
hash = dictionary[options.hash(text)] = {коллизии:0};
}
if (options.коллизии) {
if (hash.коллизии >= 2) {
if (!hash.варианты){ hash.варианты = {}; }
hash.варианты[text.join('')] = true;
}
} else {
++hash.коллизии;
}
}
options.add = (dictionary, from, to)=>{
var obj = dictionary;
[from,to,'.'].forEach(_=>{
var next = obj[_];
obj = next = next?next:(obj[_]={});
});
}
options.addBrand = (name)=> options.addHash(options.бренды, name);
options.addTypo = (from,to)=>
from.forEach(f=>to.forEach(t=>
f != t ? options.add(options.опечатки, f,t) : null
));
options.hash = (string) => {
let hash = 0;
for (const char of string) {
hash = (hash << 5) - hash + char.charCodeAt(0);
hash |= 0; // Constrain to 32bit integer
}
return hash;
};
options.valid = (ctx,word)=>{
var коллизии = options.бренды[options.hash(word)];
if (коллизии && коллизии.коллизии > 1) {
return !!коллизии.варианты[word.join('')];
}
return !!коллизии;
}
options.word = (ctx,word,maxTypos)=>{
if (options.valid(ctx,word)){
ctx.варианты.push({
опечаток: 0,
правильно: word.join(''),
оригинал: word.join('')
});
if (maxTypos == 0) {
return true;
}
}
if (maxTypos >= 1) {
word.forEach((_,i)=>{
var список = options.опечатки[_];
if (!список){return;}
var опечатки = Object.keys(список);
опечатки.forEach(оп=>{
var nw = [...word];
nw[i] = оп;
if (options.valid(ctx,nw)){
ctx.варианты.push({
опечаток: 1,
правильно: nw.join(''),
оригинал: word.join('')
});
}
});
});
}
if (maxTypos >= 2) {
word.forEach((_,i)=>{
var список = options.опечатки[_];
if (!список){return;}
var опечатки = Object.keys(список);
word.forEach((__,j)=>{
if (i<=j){return;}
var списокJ = options.опечатки[__];
if (!списокJ){return;}
var опечаткиJ = Object.keys(списокJ);
опечатки.forEach(оп=>{
опечаткиJ.forEach(опJ=>{
var nw = [...word];
nw[i] = оп;
nw[j] = опJ;
if (options.valid(ctx,nw)) {
ctx.варианты.push({
опечаток: 2,
правильно: nw.join(''),
оригинал: word.join('')
});
}
});
});
});
});
}
return !!ctx.варианты.length;
}
options.formatMinutesToTime = (totalMinutes)=> {
const hours = Math.floor(totalMinutes / 60);
const minutes = totalMinutes % 60;
const formattedHours = String(hours).padStart(2, '0');
const formattedMinutes = String(minutes).padStart(2, '0');
return `${formattedHours}:${formattedMinutes}`;
}
}
words = dtime:time description
&{console.log('brends', options.бренды); return true;}
_ time:time ws:(w:word _ {return w;})+
{
var времяНастройки = options.formatMinutesToTime((time-dtime) / 1000);
var времяРазбора = options.formatMinutesToTime((Date.now()-time) / 1000);
return {результат:ws, времяНастройки, времяРазбора};
}
ctx = &(.) {return {варианты:[]};}
word = ctx:ctx word:alphabet+ &{return options.word(ctx,word,3);} { return ctx;}
_ = [ \t\r\n]*
alphabet = s:[0123456789a-zA-Zа-яА-ЯёЁ\!\-\+\*\"\'] {return s;}
string = s:alphabet+ {return s;}
letter = s:alphabet+ {return s;}
brand = s:string{return s;}
addBrand =
"названия" _ (s:brand { options.addBrand(s); return null;})
("," _ s:brand { options.addBrand(s); return null;})* _ "." {return null;}
addTypo =
"опечатки" _ (from:letter _ "->" _ to:letter { options.addTypo(from,to); return null;})
("," _ from:letter _ "->" _ to:letter { options.addTypo(from,to); return null;})* _ "." {return null}
predescription = desc:((addBrand / addTypo) _)+ {return desc}
description = &predescription &{ return options.коллизии = true;} desc:((addBrand / addTypo) _)+ {return desc}
time = &(.) { return Date.now(); }
Расширил алфавит русскими буквами, цифрами, знаками !-+*.
При коллизии хешей, сравнение дополнительно делается по содержимому строки.
Добавил чтение конфигурации парсера непосредственно из файла разбора:
Здравствуйте, F3V, Вы писали:
F3V>По идее, количество вероятных ошибок должно зависеть от длины слова, но пусть будет пока две.
Именно так.
Но современные системы ограничиваются двумя ошибками из-за невозможности преодоления комбинаторного взрыва на большем кол-ве ошибок.
Исключение составляет алгоритм SymSpell, но работает по разному для опечаток из разряда пропущенных и добавленных, в этом его слабость.
F3V>Уточнённая грамматика
Занятный инструмент.
Без стёба. ))
Вот бы нагенерить хотя бы пол-миллиона ключевых слов из алфавита и натравить на разбор десятков различных предложений, где встречаются ключевые слова.
В этой предметной области, смотрю, сравнивают различные алгоритмы/реализации по времени нечеткого поиска 1000 запросов в словаре из полумиллиона ключевых слов.
(т.е. десяток примеров надо будет прогнать в цикле 100 раз).
(Если PEG-парсер покажет хоть сколько-нибудь интересные результаты, то можно будет попробовать переписать сгенерированный код на компилируемом языке, например на плюсах, и опять проверить)
Но для опечаток-перестановок (поменяли соседние символы местами) расстояние между словами считается 1, но SymSpell для этого случая требует 2 удаления, т.е. рассматривает этот вид опечаток как расстояние 2. ))
И для опечаток, когда добавлен случайно лишний символ, он на каждый добавленный символ уменьшает покрываемое расстояние других опечаток на 1.
====
Однако, SymSpell относительно дешево позволяет сделать не 2 опечатки, а 3, что покрывает функциональность других алгоритмов с порогом расстояния 2, для тех ситуаций, где встречается не более одной опечатки-добавления.
Здравствуйте, Janus, Вы писали:
J>фонетические алгоритмы здесь?
Ага — это первое что приходит в голову (и тут тоже многим сходу пришло) — это использовать такое св-во, как "наиболее типичные ошибки".
Фонетические алгоритмы как раз из этой области — производят подстановки "похожих" символов и их сочетаний.
Целью является уменьшение алфавита, ес-но.
