Fordított index - Inverted index

A számítástechnikában az invertált index (más néven feladási fájl vagy invertált fájl ) egy adatbázis-index, amely a tartalomtól, például szavaktól vagy számoktól való leképezést tárolja a táblázatban , dokumentumban vagy dokumentumkészletben. dokumentumok (nevük ellentétben a továbbított indexekkel , amelyek dokumentumokról tartalomra térképeznek fel). Az inverz index célja, hogy lehetővé tegye a gyors teljes szöveges keresést , fokozottabb feldolgozás árán, amikor egy dokumentumot hozzáadnak az adatbázishoz. Az invertált fájl lehet maga az adatbázisfájl, nem pedig az indexe. Ez a legnépszerűbb adatszerkezet, amelyet a dokumentumok visszakeresésében használnak rendszerek, amelyeket nagy léptékben használnak, például keresőkben . Ezenkívül számos jelentős általános célú nagyszámítógép- alapú adatbázis-kezelő rendszer fordított lista architektúrákat használt, beleértve az ADABAS , a DATACOM / DB és a 204 modellt .

Az invertált indexeknek két fő változata létezik: A rekordszintű fordított index (vagy invertált fájlindex, vagy éppen fordított fájl ) tartalmazza az egyes szavakra vonatkozó hivatkozások listáját a dokumentumokhoz. A szószintű fordított index (vagy a teljes fordított index vagy a fordított lista ) emellett tartalmazza az egyes szavak pozícióit a dokumentumban. Ez utóbbi forma több funkcionalitást kínál (például kifejezéskeresés ), de nagyobb feldolgozási erőre és helyre van szükség a létrehozásához.

Alkalmazások

Az inverz index- adatstruktúra egy tipikus keresőmotor-indexelő algoritmus központi eleme . A keresőmotor megvalósításának célja a lekérdezés sebességének optimalizálása: keresse meg azokat a dokumentumokat, ahol az X szó előfordul. Amint kifejlesztésre került egy előre mutató index , amely dokumentumonként tárolja a szavak listáját, akkor ezután megfordul, hogy kifejlesszen egy fordított indexet. Az előreindító index lekérdezéséhez az egyes dokumentumok és az egyes szavak egymás utáni iterációjára van szükség az egyező dokumentum ellenőrzéséhez. Az ilyen lekérdezés végrehajtásához szükséges idő, memória és feldolgozási erőforrások nem mindig technikailag reálisak. Ahelyett, hogy a dokumentumonként szereplő szavakat felsorolná a továbbított indexben, kifejlesztik az invert index indexstruktúrát, amely szavanként sorolja fel a dokumentumokat.

A fordított index létrehozásával a lekérdezés most megoldható úgy, hogy a fordított indexben az ID szóra ( véletlen hozzáféréssel ) ugrik .

A számítógép előtti időkben a fontos könyvek konkordanciáit manuálisan állították össze. Ezek gyakorlatilag fordított indexek voltak, kis mennyiségű kísérő kommentárral, amelyek előállításához hatalmas erőfeszítésekre volt szükség.

A bioinformatikában az invertált indexek nagyon fontosak a szekvenált DNS rövid fragmenseinek szekvencia összeállításában . A fragmens forrásának megtalálásának egyik módja az, ha egy referencia DNS szekvenciával szemben keresi. Kis számú eltérés (a szekvenált DNS és a referencia DNS közötti különbségek vagy hibák miatt) elszámolható úgy, hogy a fragmentumot kisebb fragmentumokra osztjuk - valószínűleg legalább egy részfrakció megegyezik a referencia DNS szekvenciával. Az illesztéshez meg kell fordítani egy bizonyos hosszúságú összes szubsztrátum invertált indexét a referencia DNS szekvenciából. Mivel az emberi DNS több mint 3 milliárd bázispárt tartalmaz, és minden indexhez DNS-szubsztrátumot, magához az indexhez pedig 32 bites egész számot kell tárolnunk, valószínűleg egy ilyen invertált index tárolási követelménye valószínűleg tíz gigabájt lenne.

Tömörítés

Történelmi okokból az invertált listatömörítést és a bitképtömörítést külön kutatási vonalakként dolgozták ki, és csak később ismerték el, hogy lényegében ugyanazt a problémát oldják meg.

Lásd még

Bibliográfia

  • Knuth, DE (1997) [1973]. "6.5. Visszaállítás másodlagos kulcsokon". A számítógépes programozás művészete (harmadik kiadás). Olvasás, Massachusetts : Addison-Wesley . ISBN   0-201-89685-0 .
  • Zobel, Justin; Moffat, Alistair; Ramamohanarao, Kotagiri (1998. december). Msgstr "Invertált fájlok és aláírási fájlok a szöveg indexeléséhez". ACM-tranzakciók az adatbázis-rendszereken . New York: Egyesület a Számítástechnikai Gépekhez . 23. (4): 453–490. doi : 10.1145 / 296854.277632 . S2CID   7293918 .
  • Zobel, Justin; Moffat, Alistair (2006. július). Msgstr "Fordított fájlok a szöveges keresőmotorok számára". ACM számítási felmérések . New York: Egyesület a Számítástechnikai Gépekhez . 38 (2): 6. doi : 10.1145 / 1132956.1132959 . S2CID   207158957 .
  • Baeza-Yates, Ricardo ; Ribeiro-Neto, Berthier (1999). Modern információ-visszakeresés . Olvasás, Massachusetts : Addison-Wesley Longman. o. 192. ISBN   0-201-39829-X .
  • Salton, Gerard; Fox, Edward A .; Wu, Harry (1983). Msgstr "Kiterjesztett logikai információkeresés". Commun. ACM . ACM. 26 (11): 1022. doi : 10.1145 / 182.358466 . hdl : 1813/6351 . S2CID   207180535 .
  • Információkeresés: Keresőmotorok megvalósítása és kiértékelése . Cambridge, Massachusetts: MIT Press. 2010. ISBN   978-0-262-02651-2 .

Hivatkozások

Külső linkek