�ݺ�ߣ

Повнотекстовий пошук: кішочки

Проблема
Давним-давно, в далекій-далекій галактиці…
...був проект на Magento, у якого були проблеми з пошуком...

Проблема
Серйозні
проблеми...

Наївне розв’язання
Я реалізував рішення, яке працювало:
SELECT * FROM products WHERE title LIKE '%ipod%' OR title LIKE '%nano%' OR
title LIKE '%ipod nano%' OR description LIKE '%ipod%' OR description LIKE
'%nano%' OR description LIKE '%ipod nano%';

Яке насправді більш схоже було на це:
SELECT product_id FROM (
SELECT
products.id AS product_id,
2 AS score
FROM products
WHERE title LIKE '%ipod nano%' OR description LIKE '%ipod nano%'
UNION
SELECT
products.id,
1 AS score
FROM products
WHERE title LIKE '%ipod%' OR title LIKE '%nano%' OR description LIKE '%ipod%' OR description LIKE '%nano%'
ORDER BY
score DESC
) AS T1;

Яке насправді більш схоже було на це:
SELECT product_id FROM (
SELECT
products.id AS product_id,
2 AS score
FROM products
WHERE title LIKE '%ipod nano%' OR description LIKE '%ipod nano%'
UNION
SELECT
products.id,
1 AS score
FROM products
WHERE title LIKE '%ipod%' OR title LIKE '%nano%' OR description LIKE '%ipod%' OR description LIKE '%nano%'
ORDER BY
score DESC
) AS T1;
І воно реально працювало
на продакшні!

Спробуйте вгадати, які були проблеми у такого підходу 😉

1. Перформанс
Довгі пошукові запити, багато продуктів, довгі описи продуктів - все
приводило до деградації видайності.
Проблеми наївного підходу

2. Все ще “погані” результати пошуку (принаймні, не перша сторінка)

3. Складніші кейси не підтримувались
Помилки при наборі тексту (typos), варіації слів (cables ↔ cable), скорочення
(S.T.A.L.K.E.R. ↔ stalker), вже не говорячи про синоніми та ін.

Поки воно працює - не чіпай його!

Як працюють всі ці гугли?
І ось, нещодавно, я відкрив для себе цілий світ науки про Information
Retrieval

Сьогодні в програмі
Information Retrieval - досить обширний і глибокий розділ науки, тож я розкажу
тільки про такі (цікаві?) теми:
● Як зберігати дані
● Як сортувати результати
● Нечіткий пошук

Сьогодні в програмі
Гуглити за такими запитами:
● Inverted index
● TF-IDF
● Vector-space model
● Levenshtein & Levenshtein-Damerau distance

Декілька понять
● Документ
● Терм
● Індекс

Документ
Документ - це текст, який ми скормлюємо пошуковому двіжку разом з його
айдішником (тексту), щоб пізніше зрозуміти що конкретно було знайдено.
A complete numerical series is followed by
an incomplete numerical series. You need
to solve that incomplete numerical series in
the same pattern in which the complete
numerical series is given.
оце все - документ

Терм
Терм - це одне слово, фраза або скорочення з документу.
Кожне з них - терм

Індекс
Індекс - це структура даних, в якій ми зберігаємо документи, для пошуку.
{
"numerical": 4,
"series": 4,
"is": 2,
"incomplete": 2,
"complete": 2,
"in": 2,
"the": 2,
"need": 1,
"a": 1,
"you": 1,
"followed": 1,
"to": 1,
...
}

Нахіба нам індекс?
Табличка в базі даних:
1 -> long long long text
2 -> shorter but still long text
3 -> extremely, unbelievably long text
Inverted index:
term -> 1, 3, 155, 20195
other_term -> 2, 3, 14, 29, 31, 20114
rare_term -> 19852, 30421

Inverted index:
term -> 1, 3, 155, 20195
other_term -> 2, 3, 14, 29, 31, 20114
rare_term -> 19852, 30421
Запит буде порівняно з кожним
документом, по черзі.

Для кожного терму з запиту
можна досить швидко
витягнути всі документи, які
мають в собі цей терм.
Inverted index:
term -> 1, 3, 155, 20195
other_term -> 2, 3, 14, 29, 31, 20114
rare_term -> 19852, 30421

Пошук в Lucene Пошук в БД

Додавання і видалення даних в/з індексу повільне, але пошук - швидкий

Inverted index: деякі реалізації
Map<String, List<Long>> - кожному терму відповідає список айдішників
документів, які мають цей терм.
{
"term1": ["doc1", "doc2"],
"term2": ["doc2", "doc3"]
}

Map<String, Map<String, Long>> - кожному терму відповідає список
айдішників документів і кількість цього терму в цьому документі. Розширена
версія, (трошки) прискорює обчислення (див. далі)
{
"term1": { "doc1": 1, "doc2": 3 },
"term2": { "doc2": 4, "doc3": 1 }
}

Matrix2D<Long> - двовимірний масив, кожному айдішнику документа (одна
вісь матриці) відповідає кількість терма (друга вісь матриці) в цьому
документі. Швидкі обчислення, але жере купу лишньої пам’яті.
doc1 doc2 doc3
term1 1 3 0
term2 0 4 1

Map<String, Map<String, List<Long>>> - терм - документ і позиції
цього терма в цьому документі. Дозволяє шукати по фразах.
{
"term1": { "doc1": [0], "doc2": [0,2,6] },
"term2": { "doc2": [1,3,4,5], "doc3": [0] }
}

Створюємо inverted index
1. Розбиваємо текст на слова (отримаємо список слів; це називається
“аналіз документу”)
2. Заповнюємо хешмапу індексу відповідно (як ключ беремо слово, як
значення робимо або список ID документів, або кількість цього слова в
документі, або шо)
Для оптимізації, можна зліпити ці два кроки в один цикл/map-reduce.

Пошук по індексу
Дано:
● List<String> - наш пошуковий запит; слова які ТРЕБА або БАЖАНО
щоб були у знайдених документах
● Index - індекс 😐

const result = new Set();
for (let queryTerm of query) {
const docs = index.get(queryTerm);
for (let docId of docs) {
result.add(docId);
}
}
Пошук в індексі: шукаємо БУДЬ-ЯКИЙ терм

Пошук в індексі: шукаємо БУДЬ-ЯКИЙ терм
const result = [];
for (let i = 0; i < query.length; ++i) {
result = _.union(index.get(query[i]));
}

const result = new Set(index.get(query[0]));
const queryTerm = query[i];
const docs = index.get(queryTerm);
for (let docId of result) {
if (!docs.has(docId)) {
result.delete(docId);
}
}
}
Пошук в індексі: шукаємо ВСІ терми

Пошук в індексі: шукаємо ВСІ терми
const result = index.get(query[0]);
result = _.intersection(index.get(query[i]));
}

Пошук: крок 2
Знайти документи не складно. Складно посортувати їх шоб було гарненько.

TF-IDF
TF - term frequency
IDF - inverse document frequency

Число, яке показує наскільки терм важливий для конкретного документу
TF-IDF

TF-IDF
Нехай у нас є такі два тексти:
Farscape is my favourite series. It’s unique
and, as far as i know, there is no similar
series out there, so give it a try if you want
to see something unique. Some say Firefly,
Andromeda, Lexx and so on are similar.
But those series are very different and
share nothing in common with farscape in
my opinion.

Наскільки релевантне слово “series” для кожного з них?
TF-IDF

TF-IDF
Вот еті рєбята:
my opinion.

Примітка: TF-IDF простіше рахувати використовуючи розширені варіанти
індексу, як от цей:
// term -> { documentId -> number of occurrences }
const index: Map<String, Map<Number, Number>>;
// documentId -> [ term ]
const documents: Map<Number, List<String>>;
TF-IDF

TF
Глянем на аналіз цих двох текстів:
{
"series": 3,
"and": 3,
"there": 2,
"unique": 2,
"farscape": 2,
"as": 2,
"my": 2,
"similar": 2,
"so": 2,
"is": 2,
"are": 2,
"in": 2,
"favourite": 1
}
{
"numerical": 4,
"series": 4,
"is": 2,
"incomplete": 2,
"complete": 2,
"in": 2,
"the": 2,
"need": 1,
"a": 1,
"you": 1,
}

TF
tf = (term, docId) => index.get(term).get(docId) / documents.get(docId).length;
Співвідношення кількості цього терма в документі до кількості всіх слів в
документі.

TF-IDF
Індекс для кожного з цих текстів:
{
"numerical": 4,
"series": 4,
"is": 2,
"incomplete": 2,
"complete": 2,
"in": 2,
"the": 2,
"need": 1,
"a": 1,
"you": 1,
}

TF-IDF
my opinion.
{
"series": 3,
"and": 3,
"there": 2,
"unique": 2,
"farscape": 2,
"as": 2,
"my": 2,
"similar": 2,
"so": 2,
"is": 2,
"are": 2,
"in": 2,
"favourite": 1
}
Індекс для кожного з цих текстів:

IDF
А тепер зиркнемо на весь індекс:
{
"a": [1, 2],
"series": [1, 2],
"is": [1, 2],
"you": [1, 2],
"to": [1, 2],
"in": [1, 2],
"an": [1],
"incomplete": [1],
"opinion": [2],
"need": [1],
"numerical": [1],
}

IDF
idf = (term) => Math.log(index.size / index.get(term).size)
Логарифм від співвідношення кількості слів в індексі до кількості документів, в
яких є даний терм.

// term -> { documentId -> number of occurrences }
let index: Map<String, Map<Number, Number>>;
let documents: Map<Number, List<String>>;
tf = (term, docId) => index.get(term).get(docId) / documents.get(docId).length;
idf = (term) => Math.log(1 + (index.size / index.get(term).size));
tf_idf = (term, docId) => tf(term, docId) * idf(term);
TF-IDF

tf_ifd("series", doc1) = 0.43886417827898777
tf_idf("series", doc2) = 0.17592400249976667
Тобто, слово “series” значно
менш релевантне для другого
документу
TF-IDF

tf_ifd("series", doc1) = 0.43886417827898777
tf_idf("series", doc2) = 0.17592400249976667
Тобто, слово “series” значно
менш релевантне для другого
документу
ШТА?
TF-IDF

А проблеми роблять ось такі штуки:
{
"and": 3, "there": 2, "as": 2, "my": 2,
"so": 2, "is": 2, "are": 2, "in": 2,
"it’s": 1, "it": 1, "a": 1, "if": 1,
"to": 1, "on": 1, "i": 1, "but": 1,
"those": 1, "with": 1
}
TF-IDF

tf_ifd("series", doc1) = 0.6040849772288726
tf_idf("series", doc2) = 0.2517020738453635
TF-IDF: фільтруємо слова-паразити

TF-IDF це канєшно круто, але воно працює тільки для одного слова і одного
документа. А якшо ми робим гугль, і у нас ТИСЯЧІ, МІЛЬЙОНИ документів?
Чутка математики

Vector-space model
Вумні дядьки взяли і використали вектори (по суті - просто масив чисел, з
парою хитрих операцій).

Vector-space model
Але ці дядьки (як на мене) лажанулись, намагаючись пояснити цю штуку

Vector-space model
Якщо ми представимо кожен документ і запит як вектор, ми зможемо
визначити наскільки вони схожі, взявши косинус кута між ними.

Vector-space model
Безполєзно малювати ще одну картінку, так шо хавай, піпл, табличку:
term doc ID doc1 doc2 query
series 1 1 1
you 1 1 0
numerical 1 0 0
andromeda 0 1 1
occurrences

Vector-space model
query = "series andromeda";
similarity(doc1, query) = cos((1, 1, 1, 0), (1, 0, 0, 1)) = 0.4
series 1 1 1
you 1 1 0
numerical 1 0 0
andromeda 0 1 1

Vector-space model
query = "numerical series";
series 1 1 1
you 1 1 0
numerical 1 0 1
andromeda 0 1 0

Vector-space model
query = "series numerical";
Проблема в тому, що перестановка слів в запиті не дає нікакого еффекту.

Після всього вищесказаного, у вас має
виникнути одне питання

Ліпим все до купи
class Index {
private index: Map<String, Map<String, Number>>;
private documents: Map<String, Array<String>>;
// documentId -> text
private originals: Map<String, String>;
...
}

similarity(doc1: Array<String>, doc2: Array<String>): Number {
let score = 0;
for (const term of this.index.keys()) {
score += this.tf(term, doc1) * this.tf(term, doc2);
}
return score;
}

public search(query: String) {
const queryTerms = this.parse(query);
const scores = new Map(); const counts = new Map();
for (const term of queryTerms) {
const matches = this.index.get(term);
for (const docId of matches.keys()) {
scores.set(docId, scores.get(docId) + this.similarity(queryTerms, this.documents.get(docId)));
counts.set(docId, counts.get(docId) + 1);
}
}
for (const docId of scores.keys()) {
results.set(docId, scores.get(docId) * counts.get(docId));
}
}

Бонус: did you mean: *that*?

Нечіткий пошук
Прикольна фіча, яка робить гугл “розумним” називається “нечіткий пошук”
(fuzzy search) - коли алгоритм знаходить слова, подібні до слова з запиту
(враховуючи всякі очєпяткі, синоніми і т.д.).

Нечіткий пошук
Простий і ефективний алгоритм який рахує наскільки два слова подібні між
собою - відстань Левенштейна (з розширенням, відстань Левенштейна-
Дамерау)

Відстань Левенштейна
Рахує скільки “операцій” треба зробити зі словом А щоб отримати слово Б.

Ось ці операції:
● Додати один символ
● Видалити один символ
● Замінити один символ на інший

perference -> preference (2 заміни)
perfmance -> performance (2 додання)
battlestart -> battlestar (1 видалення)

levenshtein(s1, s2) {
let v0 = []; let v1 = [];
for (let i = 0; i <= s1.length; ++i) { v0[i] = i; }
for (let i = 0; i < s2.length; ++i) {
v1[0] = i + 1;
for (let j = 0; j < s1.length; ++j) {
v1[j + 1] = Math.min(v0[j + 1] + 1, v0[j] + 1, v0[j] + (s1[i] != s2[j]));
}
let tmp = v0; v0 = v1; v1 = tmp;
}
return v0[s1.length];
}

Відстань Левенштейна-Дамерау
Те ж саме, що і відстань Левенштейна, тільки рахує ще одну операцію:
● Додати один символ
● Видалити один символ
● Замінити один символ на інший
● Поміняти два сусідні символи місцями

perference -> preference (1 перестановка)
perfmance -> performance (2 додання)
battlestart -> battlestar (1 видалення)

levenshtein_damerau(s1, s2) {
let v0 = []; let v1 = [];
for (let i = 0; i <= s1.length; ++i) { v0[i] = i; }
for (let i = 0; i < s2.length; ++i) {
v1[0] = i + 1;
for (let j = 0; j < s1.length; ++j) {
v1[j + 1] = Math.min(v0[j + 1] + 1, v0[j] + 1, v0[j] + (s1[i] != s2[j] ? 1 : 0));
if (i > 0 && j > 0 && s1[i] == s2[j - 1] && s1[i - 1] == s2[j]) {
v1[j + 1] = Math.min(v1[j + 1], v0[j - 1]);
}
}
let tmp = v0; v0 = v1; v1 = tmp;
}
return v0[s1.length];
}

�ݺ�ߣ

Повнотекстовий пошук - кішочки

More Related Content

Повнотекстовий пошук - кішочки