Здравствуйте, 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] проводим сравнение всерьез — по Левенштейну, скажем.

Здравствуйте, 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] проводим сравнение всерьез — по Левенштейну, скажем.