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

Question

[BadThings]

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

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

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

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

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

Или же я в чем то неправ? Как оптимальнее всего поступить?

Comments

[Сергей П]

1. Задача единоразовая? Или часто нужно делать? А если часто, то что меняется? Новые строки, новые номера?
   
2. Есть лимиты на время выполнения задачи? Может быть поставить обработку на ночь - это приемлемое решение?
   
3. Встречаются ли пробелы в номерах?
   

[BadThings]

Сергей Паньков,
1. Задача повторяющаяся. Один запуск программы (UI) = один список строк (до 100, в среднем 50), в которых осуществляют поиск = один прогон. Каждый запуск программы - новые строки, общий список парт-номеров не изменяются, но в каждой строке может быть любой из 200к+ парт-номеров.
2. В пределах юзер-френдли. Можно сказать думаю что до 10 минут для до 100 различных строк
3. Все парт-номера и текст будет урезаны. В силу того что описание пишет человек и может проставить дополнительный пробел/точку/тире -> это уже не 100% совпадение с реальным парт номером. Как именно, пока не ясно. точно уберу пробелы, тире/точки. это Важно т.к. таких ошибок до 30% встречается

В идеале добавить в алгоритм возможность подобрать несколько наиболее совпадающих парт-номеров. Снова вступает шанс человеческой ошибки. Но данный пункт не критичен т.к. таких ошибок менее 1%

Answer 1

[Сергей П]

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" - попадут в кэш с информацией о том, что их нет в БД.
Остальные слова, которых уже будет не так много, будут морфироваться и с логарифмической сложностью искаться в БД.
Думаю всё будет работать просто мгновенно. В любом случае локальным персистентным кэшем несуществующих в БД слов можно закидать любые тормоза в контексте вашей задачи.

Answer 2

[longclaps]

Или

Comments

[Владимир Олохтонов]

Мне кажется примерно тут и проходит граница между теми кто знаком хотя бы с классическими алгоритмами и теми, кто этого знакомства избежал.

Вторые вынуждены изобретать сложные системы там, где первые воспользуются готовым компактным решением.

[longclaps]

Владимир Олохтонов, да, притом бесконечные камлания на хабре "я программирую 15 лет и ни разу мне не потребовался алгоритм ***".

Answer 3

[xmoonlight]

В базе данных, создайте рядом колонку и заполните её заранее, вытащив парт-номер из строки.
/(?:[0-9A-Z-]+[-]{0,1}){8}/u
Затем, просто выполняйте поиск по этой колонке.
Можно создать триггер, который будет заполнять эту колонку автоматически при добавлении новых товаров.