Нечіткий пошук за назвами
Добридень. Проблема пошуку, послуг або продукту виникає на переважній більшості сайтів. І в основному реалізація такої можливості обмежуються пошуком за точним словом, яке ввели в пошуковому рядку.
Якщо є час, і замовник хоче трохи більшого, то гуглять реалізацію найпопулярнішого алгоритму (яким є «відстань Левенштейна») і вписують його.
У цій статті, я опишу сильно доопрацьований алгоритм, заснований, щоправда, на відстані Левенштейна, і наведу приклади коду на C# нечіткого пошуку за назвами, наприклад: кафе, ресторанів чи деяких сервісів… Загалом все, що можна перерахувати і має від одного до одного кількох слів у своєму складі:
"Яндекс", "Mail", "ProjectArmata", "world of tanks", "world of warships", "world of warplanes" і т.д. Тим, хто незнайомий з алгоритмом, я рекомендую прочитати спочатку статті "Реалізація нечіткого пошуку", "Нечіткий пошук у тексті та словнику" або його опис у моєму викладі під слайдером.
Відстань Левенштейна є найбільш популярним алгоритмом мережі для знаходження ступеня відмінності між двома словами. А саме яку мінімальну кількість дій необхідно зробити для отримання з першого рядка другого.
Таких дій лише три:
• Видалення • Вставка • Заміна
Наприклад, для 2-х рядків "CONNECT" і "CONEHEAD" можна побудувати наступну таблицю перетворень:
Теоретично, ціни операцій можуть залежати від виду операції (вставка, видалення, заміна) та/або від символів, що беруть участь у ній. Але в загальному випадку:
w(a, ε) — ціна видалення символу «a», дорівнює 1 w(ε, b) — ціна вставки символу «b», дорівнює 1 w(a, b) — ціна заміни символу «a» » на символ «b», дорівнює 1
Скрізь ставлять одиниці.
А з точкизору математики розрахунок виглядає так.
Нехай S1 і S2 - два рядки (довжиною M і N відповідно) над деяким алфавітом, тоді редакційну відстань (відстань Левенштейна) d(S1, S2) можна підрахувати за наступною формулою рекурентної:
"Дефолтну реалізацію" алгоритму Левенштейна зробили два математики Вангер і Фішер [не плутати з шахістом].
І виглядає це на С# так:
А візуально робота алгоритму для слів «Арештант» та «Дагестан» представляється так:
Крайній правий-нижній кут матриці показує, як сильно відрізняються слова. З матриці, що в даному конкретному випадку різниця між словами складає 3 умовні папуги.
Якщо незрозуміло, то подивимося на ці слова в іншому поданні:
_ АРЄ С Т А Н Т Д АГЕ С Т А Н _
Таким чином, виходить, щоб перетворити слова "Арештант" і "Дагестан", потрібно одну літеру "Д" додати, одну літеру "Р" замінити на "Г" та літеру "Т" видалити. Т.к. всі дії мають вагу 1, то виходить відмінність у словах становить 3 папуги.
Якщо слова повністю збігаються, то відстань буде 0. Ось і вся теорія все геніальне просто.
І здавалося б – ось воно! Все придумано за нас і робити взагалі нічого не треба, але є проблема.
1) Брати ваговий коефіцієнт 1 завжди – не зовсім правильно, бо ймовірність друкарської помилки залежить від кількох конкретних факторів: відстані клавіш на клавіатурі, фонетичні групи, та й навіть банальної швидкості набору символів. 2) Ідея Левенштейна призначена для «знаходження відмінностей між словами», а не частини слів, що для динамічного результатів, що видаються, у міру введення літер критично. 3) Назви сервісів мають у своєму складі більше одного слова, то людина може просто непам'ятати, в якому порядку вони йдуть.
Також врахуємо ще кілька факторів, типу:
• розкладка клавіатури іншою мовою • транслітерації символів
Саме ці проблеми ми намагатимемося вирішити у цій статті.
Для початку, давайте домовимося, що всі слова ми будемо приводить до одного єдиного регістру. У своїй версії коду я вибрав нижній регістр, це буде відображено в довідках, які нам знадобляться (дані довідники будуть наведені в ході опису). У самій статті я вдаватимуся з різним стилям написання, наприклад, до CamelCase - ProjectArmata, але це зроблено виключно для зручності сприйняття людиною, з точки зору аналізу регістр один (нижній). І ще за основу ми візьмемо не класичний, а оптимізований варіант коду для знаходження відстані Левенштейна звідси:
Дещо скоригуємо його, прибравши зміни порядку слів. Для алгоритму Левенштейна порядок слів немає значення, але він буде важливий з інших причин. У результаті отримали таке:
Почнемо покращення алгоритму пошуку із зміни вагових коефіцієнтів. Для початку зробимо, коефіцієнти вставки та видалення рівним 2.
Тобто. поміняються рядки:
А ось рядок розрахунку коефіцієнта заміни символів, ми, перетворивши на функцію CostDistanceSymbol:
І враховуватимемо два фактори:
1) Клавіатурна відстань 2) Фонетичні групи
У зв'язку з цим, для зручнішої роботи з об'єктами source і target ми перетворимо їх на об'єкт:
Для цього знадобляться такі допоміжні довідники:
Співвідношення кодів клавіш українськомовної клавіатури:
Співвідношення кодів клавіш для англомовної клавіатури
Завдяки цим двом довідникам, говорячи математичною мовою, ми можемоперетворити два різні простори символів в один єдиний універсальний.
І на ньому будуть справедливі наступні співвідношення:
private static SortedDictionary DistanceCodeKey = New SortedDictionary Ремарка
Оптимізований код, який ми взяли за основу, має наступний вид ініціалізації матриці відстані: var distance = new int[2, m + 1];
Тому ця ділянка коду «distance[(i — 2) % 3, …», працювати в поточному вигляді не буде, правильний варіант функції я наведу в кінці статті.
Таким чином, ми виконали перший пункт з доопрацювання коду. Переходимо до другого пункту. Нагадаємо, що ідея Левенштейна призначена для «знаходження відмінностей між словами», а не частини слів, що для динамічного результатів, що видаються, у міру введення букв, є критичним.
Наприклад, у довіднику є два слова:
Ввівши в рядок пошуку запит «Pro» ми отримаємо на виході «Як» як більш пріоритетне, тому що заміна двох символів і видалення одного складе всього 3 папуги (з урахуванням одиничних коефіцієнтів та класичного алгоритму Левенштейна, без наших доробок), а додавання частини слова «jectArmata» 10 папуг.
Найбільш логічним у цій ситуації є порівняння не лише слова, а лише частини шуканого слова із веденим рядком.
Т.к. пошуковий запит складається з трьох символом Pro, ми візьмемо перші три символи від звіряється слова ProjectArmata, тобто. "Pro" і отримаємо 100% збіг. Для цього конкретного випадку - ідеально. Але розглянемо ще кілька варіантів. Допустимо, у нас в базі, є наступний набір слів:
• «Комуналка» • «Конвеєр» • «Колонія» • «Косметика»
Пошуковий запит виглядатиме так «Ком». Як наслідок слова матимуть такі коефіцієнтизбіги:
Комуналка - 0 Конвеєр - 1 Колонія - 1 Косметика - 1
Якщо зі словом «Комуналка» все нормально, то решта трьох слів виглядає якось однаково… Хоча видно, що, можливо, людина описалася в одній літері і вона шукає «Косметика», а не Конвеєр чи Колонія. А наше завдання полягає в тому, щоб видавати йому найкращий результат, а не просто все поспіль. Тим більше, як сказав Дамерау – більшість помилок це перестановки літер.
Для усунення подібної помилки, робимо невелике доопрацювання:
Візьмемо не перші «n» літер, а «n+1» літер, де n – кількість літер у запиті. І тоді коефіцієнти при запиті «Ком» будуть такими:
Комуналка - 1 Косметика - 1 Конвеєр - 2 Колонія - 2
«Косметику» поправили, але «Комуналка» поїхала… Але цей варіант мені подобатися більше з якихось причин. Зазвичай, якщо потрібно пошук, то спочатку інформацію показують користувачеві у вигляді списку, що випадає, під пошуковим рядком, у міру введення літер. Довжину цього список, що випадає, обмежують за розмірами 3-7 записів. Як наслідок, якщо записи всього три, то в другому варіанті з'являться: «Комуналка», «Косметика» та «Конвеєр» [т.к. він тупий перший у видачі через guid-а або просто через дати створення]. А в першому випадку буде «Комуналка», «Конвеєр», «Колонія» та жодної «Косметика», т.к. їй не пощастило з інших причин.
Звичайно, у цієї проблеми є й інші шляхи вирішення. Наприклад, сортувати спочатку, за «n» літерами, а потім взяти ті групи слів у кого збіглися індекси і додатково пересортувати «n+1» літер і можна ще раз, і ще раз… Тут вже вирішується індивідуально залежно від даних у базі , Розв'язуване завдання, обчислювальної потужності.
Давайте не будемо зараз звертати увагу навирішенні вищеописаної проблеми… Ми тільки в середині шляху і мені ще є що розповісти.
Наступний нюанс у правильній пошуковій видачі до нас приходить із часів СРСР. Тоді любили робити назви, що складаються з кількох слів, об'єднаних в одне. Та й зараз це актуально:
Споживспілка ГазПромБанк Россільгоспбанк ProjectArmata БанкУРАЛСИБ І т.д.
[П.С. я знаю, що деякі з назв пишуться через прогалину, але мені потрібно було підібрати яскраві приклади]
Але, якщо слідувати нашому алгоритму, ми завжди беремо перші «n+1» букв із слова. І якщо людина набере слово «Банк», вона не отримає адекватної видачі. Т.к. порівнювати ми будемо рядки:
Щоб знаходити слово «банк» незалежно від позиції, нам потрібно буде зробити плаваюче вікно за фразою та повертати найменший коефіцієнт:
Як можна побачити, до помилки, отриманої після підрахунку відстані Левенштейна, ми додаємо ще значення (i * 2 / 10.0). Якщо з «i*2» — все ясно, це помилка вставки букв на початку слова, як і класичному алгоритмі знаходження відстані Левенштейна, але навіщо ми її ділимо на 10? Суть у тому, що якщо ми просто залишимо «i*2», то в позовну видачу потраплять слова, які тупі менші за довжиною і ми знову втечемо від назви банків. І тому коефіцієнт доводиться ділити на 10, що скоротити це усунення. Чому саме на 10? Для нашої бази він підходив більш-менш нормально, але я не виключаю, що можна ділити на більше. Все заздрості від довжини слів і від того, наскільки слова схожі. Розрахунок найбільш відповідного коефіцієнта я наведу трохи згодом.
Зі словами, як і пошуковою одиницею, начебто розібралися, тепер переходимо до фраз. І спочатку знову кілька прикладів:
• warface • world of tanks • world of warplanes • world ofships
Давайте зрозуміємо, що нам, в принципі, потрібно від пошуку на фразі. Нам потрібно, щоб відсутні слова додавалися, зайві фрази видалялися, а також, щоб вони мінялися місцями. Десь я таке вже говорив… А, точно, згадав… На початку статті, коли розповідав про слова та функції відстані Левенштейна. Щоб не витрачати ваш час, одразу скажу, що в чистому вигляді її використовувати не вдалося, але надихнувшись їй вдалося написати код, який застосовується до фраз.
Як і за реалізації функції відстані Левенштейна, якщо одне з фраз порожня, ми повертаємо величину помилки рівне вставці чи видалення [залежно від цього, з якого боку прийшла порожня фраза] всіх букв.
Тобто. ми підсумовуємо кількість букв у фразі помножуємо на 2 (це коефіцієнт був обраний ще на початку статті для букв) і ще множимо на 100. Ось ці 100 - найсуперечливіший коефіцієнт у всьому алгоритмі. Для чого він необхідний буде більш наочно представлено трохи нижче, а потім я поясню, що в теорії його необхідно вирахувати, а не просто купувати зі стелі.
У цьому коді ми зіставляємо кожне слово з запису в базі з кожним з пошукового запиту і беремо найменші коефіцієнти для кожного слова. Сумарним коефіцієнтом для фрази є таке:
result += minRangeWord * 100 + (Math.Abs(i - minIndex) / 10.0);
Як можна бачити, вся логіка та сама, як і описана раніше, мінімальний коефіцієнт для слова minRangeWord помножуємо на наші 100 і підсумовуємо з коефіцієнтом, що показує на скільки близько слово стоїть до його найбільш підходящої позиції (Math.Abs(i — minIndex) / 10.0).
Примноження на 100 застосовується для компенсації додаткового коефіцієнта, який може виникнути при пошуку найбільш підходящої позиції пошукового слова на попередньому кроці. Як наслідок, данийкоефіцієнт можна вирахувати як найбільший між фразою в пошуковому рядку та всіма словами в базі. Чи не фразами, а саме словами. Але для цього доведеться «порожньо» виміряти відстань Левенштейна з нашими доробками, що дуже марнотратно за ресурсами.
Тобто. прогнати функцію GetRangeWord і взяти максимальне значення відхилення фрази «i*2» від місця, що найбільше підходить. І після взяти найбільше значення довести його до найближчого десятикратного числа (10, 100, 1000, 10000, 100000 і т.д.). Таким чином ми отримаємо два значення:
Перше, це значення, на яке потрібно ділити змішане слово у функції GetRangeWord. Друге, значення, яке потрібно помножити minRangeWord для компенсації попереднього зміщення. Таким чином, ми отримаємо точні показники схожості фраз. Але на практиці можна знехтувати великими відхиленнями і приблизно прикинути середнє… Що я власне й зробив.
У принципі, все. Основні питання я розібрав, що залишилося лише невелике доопрацювання «транслітерації символів». Різниця між вище описаним пошуком і пошуком по транслітерації полягає в тому, що функції CostDistanceSymbol ми не коригуватимемо значення відповіді по відстанях клавіш, т.к. видача у разі буде коректна.
Також можна відзначити, що адекватна видача результату починається з 3 символів у пошуковому рядку, якщо символом менше, краще використовувати більш незграбний метод з точним зіставленням рядків.
Далі я наведу найповніший код всього вище описаного, але спочатку:
1) Цей код написаний мною особисто у вільний від роботи час. 2) Алгоритм продуманий мною особисто у вільний від роботи час.
Дякую всім, хто прочитав. Вітається критика та поради.