Az inverted index egy adatstruktúra, ami egyszerűvé teszi egy szó (token) előfordulásainak a meghatározását egy szótár kifejezéseiben. A fordító motornak az a feladata, hogy meghatározza egy mondat összes szótárban szereplő rész kifejezését. Azt szeretnénk belátni, hogy az inverted index segítségével hatékony fordító motort tudunk építeni.
A fordító motor segítségével fordítót lehetne gyártani azáltal, hogy megmondjuk, hogy a mondat kifejezéseiből melyeket és azokat milyen sorrendben kívánjuk lefordítani és kombinálni a célnyelv mondatává. Fordítási stratégiák, heurisztikák definiálásával azonban most nem foglalkozunk.
A pontosabb érthetőség kedvéért ábrázoljuk a szótárat egy d: E -> E' függvénnyel, ahol E és E' az L és L' nyelvek kifejezéshalmazai.
Ha d(e) = e', akkor azt mondjuk, hogy az e kifejezés fordítása e'. Minden mondat kifejezések, minden kifejezés tokenek (szavak) sorozata. A fordítási problémánk abból fakad, hogy egyrészt egy mondatot értelmezni kell ahhoz, hogy felismerjük mely kifejezések alkotják, másrészt ez a felismerhető szerkezet nem feltétlenül egyértelmű. Gondoljunk csak arra az elemi algebrából jól ismert "asszociatív" esetre, amikor is egy szótár forrás nyelvének mindössze öt kifejezése van "a", "b", "c", "ab", "bc" és az "abc" mondatot kell értelmeznünk. Ekkor az {"a", "b", "c"}, {"ab", "c"}, {"a", "bc"} felbontások egyaránt helyesnek tekinthetők, azaz a fordítást bármelyikre lehetne alapozni. Szerencsére most nem kell a lehetséges felbontásokkal, átzárójelezésekkel törődnünk, hiszen csak a fordító motor definiálására vállalkoztunk, aminek mindössze az input mondat összes kifejezésével kell visszatérni:
{"a", "b", "c", "ab", "bc"}.
Egy egyszerű, de helyesen működő fordító motort nyerünk azáltal, hogy eldöntjük az input mondat összes összefüggő részhalmazáról (intervallumáról), hogy a szótárnak kifejezése-e. A példánkban szereplő "abc" mondat esetén az {"a", "ab", "abc", "b", "bc", "c"} részekről kell döntenünk. Általában egy n tokenből álló mondat esetén n(n-1)/2 részhalmazról kell dönteni. Ez nem feltétlenül rossz eljárás, azonban hosszú mondat és kifejezésekben szegény szótár esetén feleslegesen sok munkát végez.
Egy másik motor definíció lehet a következő. Először készítsünk el egy inverted index-et. Tokenizáljuk a szótár kifejezéseit és az így nyert tokenek mindegyikéhez rendeljük hozzá a szótárnak ezzel a tokennel kezdődő kifejezéseinek a halmazát. A példa szótárunk esetén az
a -> {"a", "a b"}
b -> {"b", "b c"}
c -> {"c"}
inverted index-hez jutunk.
Az inverted index elkészítése után feltehetjük, hogy kapunk egy tokenizált mondatot. A mondat lehetséges kifejezéseinek egy P halmazát fogjuk fenntartani. Egy kifejezést lehetségesnek mondunk, ha az inverted index a mondat egyik tokenjéhez rendeli. Minden lehetséges kifejezésnek van egy i életkora. Az életkor egy természetes szám, 0-val kezdődik és minden lépéssel 1-et nő.
Kezdetben P üres. Az eljárás annyi lépésből áll ahány tokenje van a mondatnak. Minden lépés elején kibővítjük P-t azokkal a kifejezésekkel (i=0 életkorral) amelyeket az aktuális tokenhez rendel az inverted index. Ezután, ha egy kifejezés életkora megegyezik a kifejezés tokenekben mért hosszával, akkor a kifejezést elfogadjuk és eltávolítjuk P-ből. A p kifejezést elutasítjuk és eltávolítjuk P-ből, ha p[i] nem egyenlő t-vel, ahol p[i] a p kifejezés i-edik tokenje, i az életkora, t pedig az aktuális token. A lépés befejeztével P azon tokenekből fog állni, amelyeket a fentiek alapján vagy nem fogadtunk el de el sem utasítottunk vagy újonnan vettünk hozzá P-hez.
Ha elfogyott az összes token visszaadjuk az elfogadott kifejezéseket.
Könnyen igazolhatjuk, hogy az algoritmus helyes, azaz a mondatban szereplő minden kifejezést megtalál és csak azokat. Műveletigénye arányos a mondatban szereplő tokenekhez az inverted index által hozzárendelt kifejezésekben szereplő tokeneknek a számával, azaz
complexity = O(sum{|p| : p ∈ inv(t), t ∈ s}),
ahol "s" az input mondat, "t" egy tokenje, "inv" az inverted index, p egy t-vel kezdődő kifejezés, |p| a p kifejezés tokenjeinek a száma, "sum" pedig az összeadás.
