Jak funguje invertovaný index?

Question

IT Interview Practice · Accepted Answer

**Invertovaný index mapuje termín na dokumenty, které jej obsahují.** Vyhledávač tak najde kandidáty bez čtení všech dokumentů od začátku do konce při každém hledání.

Představte si rejstřík na konci knihy: najdete slovo a přejdete na uvedené stránky. Ve vyhledávači nahrazují čísla stran identifikátory dokumentů.

## 1. Začněte malou kolekcí

Máme tři dokumenty a jednoduchý analyzér převádějící text na malá písmena a oddělující slova. Analyzér je sada kroků měnících text na vyhledatelné termíny.

```text
D1: Red apple
D2: Green apple
D3: Red car

apple -> D1, D2
car   -> D3
green -> D2
red   -> D1, D3
```

Původní směr vede od dokumentu ke slovům. Index jej obrací od slova k dokumentům, odtud název. Seznam odpovídajících dokumentů pro termín se nazývá posting list.

## 2. Odpovězte pomocí seznamů

Pro dotaz vyžadující red i apple načtěte oba seznamy a ponechte průnik: v obou je D1. Pro dotaz přijímající kterékoli slovo vezměte sjednocení: kandidáty jsou D1, D2 a D3.

Příklad vysvětluje shodu, ne hodnocení. Pokud vyhovuje více dokumentů, může je engine bodovat podle četnosti termínu a jeho běžnosti v kolekci. Hledání shod a určování pořadí jsou související, ale oddělené kroky.

## 3. Slaďte indexování a hledání

Dotaz musí být analyzován kompatibilně s uloženými termíny. Pokud indexování změní Red na red, ale dotaz hledá přesně Red, zamýšlená shoda může uniknout.

Vhodná analýza závisí na poli. Popisy produktů těží z textové analýzy, přesný identifikátor objednávky obvykle potřebuje přesnou shodu. Rozdělení identifikátoru na běžná slova může změnit jeho význam. Viz vysvětlení [fulltextového hledání](https://www.elastic.co/docs/solutions/search/full-text/how-full-text-works) od Elastic.

## 4. Uložte dost informací pro požadovaný dotaz

Dokument obsahující red i apple nemusí obsahovat frázi red apple. Pro fráze index potřebuje pozice slov, aby engine ověřil pořadí a sousedství.

- Identifikátory určují dokumenty obsahující termín.
- Četnosti mohou popsat počet výskytů termínu.
- Pozice podporují otázky na vzájemné umístění termínů.

Více informací umožňuje bohatší dotazy, ale zvětšuje index i práci při indexování. Vhodný index určují hledání, která má aplikace podporovat.

## 5. Pochopte cenu aktualizací

Při změně zdrojového textu se musí změnit i vyhledávací index. Systémy jako Elasticsearch spravují data v segmentech a postupně je slučují; aktualizace neznamená okamžité přepsání všech seznamů na místě. Viditelnost v hledání závisí také na refresh mechanismu.

Počítejte proto s dalším úložištěm, indexační prací a možnou prodlevou mezi zápisem dokumentu a jeho nalezením. Invertovaný index je zvlášť užitečný pro textové hledání podle termínů; není univerzální náhradou indexů pro přesné vyhledání, rozsahy nebo transakční přístup.

1. Začněte malou kolekcí

2. Odpovězte pomocí seznamů

3. Slaďte indexování a hledání

4. Uložte dost informací pro požadovaný dotaz

5. Pochopte cenu aktualizací

Související otázky