BadThings
@BadThings

Какой алгоритм использовать для поиск одной из 200к+ подстроки в строке?

Стоит задача найти текстовые ID (парт-номера) товаров в строке с описание товара. Например из строки

Накопитель SSD Samsung SATA III 500Gb MZ-76E500BW 860 EVO 2.5"

вытащить MZ-76E500BW

Те ID, которые могут встретиться, есть в SQLite базе. другие распознавать не требуется

Я смотрел в сторону поиска подстроки в строке , но насколько я понимаю это не мой случай т.к. строка очень короткая и оптимизировать для <256 символов не имеет смысл.

Или же я в чем то неправ? Как оптимальнее всего поступить?
  • Вопрос задан
  • 149 просмотров
Решения вопроса 1
trapwalker
@trapwalker
Программист, энтузиаст
BadThings, вот что могу вам предложить:
  • Разбивайте ваши строки на отдельные "слова"-претенденты для поиска. Слова ищите по отдельности в таблице.
  • Номера в таблице "нормализуйте" (не в реляционном смысле, а в смысле uppercase, удаление неоднозначных разделителей).
  • Таблицу проиндексируйте.
  • Сформулируйте стоп-критерии для слов, например по длине, наличию каких-то нехарактерных для номера символов. Для этого можно посчитать статистику по БД (min, max, set of char и т.д.).
  • Морфируйте искомые слова, например, в слове "123-0X" не ясно цифра "ноль" или буква "O" какого-то алфавита, "Икс" или кириллическая буква "Хер". Придётся строить сочетания неоднозначностей и искать их все. Но это не проблема.
  • Заведите в памяти кэш, ограниченный размером. В кэше нужно держать только слова с максимальными частотами поиска по базе. Этот кэш можно сделать персистентным и загружать в память перед поиском. Основной расчет на то, что кэшироваться будут часто встречающиеся слова, которых нет в БД.

Таким образом из строки
Накопитель SSD Samsung SATA III 500Gb MZ-76E500BW 860 EVO 2.5"

"SSD", "SATA", "III", "500GB", "860", "EVO", "2.5" - не пройдут в поиск по ограничению минимальной длинны;
"Накопитель", "Samsung" - попадут в кэш с информацией о том, что их нет в БД.
Остальные слова, которых уже будет не так много, будут морфироваться и с логарифмической сложностью искаться в БД.
Думаю всё будет работать просто мгновенно. В любом случае локальным персистентным кэшем несуществующих в БД слов можно закидать любые тормоза в контексте вашей задачи.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
В базе данных, создайте рядом колонку и заполните её заранее, вытащив парт-номер из строки.
/(?:[0-9A-Z-]+[-]{0,1}){8}/u
Затем, просто выполняйте поиск по этой колонке.
Можно создать триггер, который будет заполнять эту колонку автоматически при добавлении новых товаров.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы