LCP tömb

A LCP tömb egy adatstruktúra a számítástechnika , amely többnyire együtt használható a utótag tömb . Az „LCP” megnevezés a „ leghosszabb közös előtag ” (a német leghosszabb közös előtag ) rövidítése . A tömb magában foglalja a két lexikográfiailag egymást követő utótag leghosszabb közös előtagjának hosszát .

Számos alkalmazás létezik az LCP tömb számára a szöveges keresés és az indexelés területén, például az utótagfa létrehozása vagy a keresési minta minden előfordulásának hatékony keresése a szövegben. Az LCP tömb szükséges tárterülete lineáris a szöveg méretéhez képest, és vannak olyan algoritmusok, amelyek lineáris időben konstruálják az LCP tömböt az utótag tömb segítségével. Először Manber és Myers (1993) dolgozatában használták fel, amelyben Hgt tömbként emlegették.

meghatározás

Legyen valamilyen hosszú szöveg, és legyen a szöveg fölötti utótag tömb . Jelöli, az utótag és a hossza a leghosszabb közös előtag a két húrok és . ${\ displaystyle T = t_ {1}, t_ {2}, ..., t_ {n}}$${\ displaystyle n}$${\ displaystyle A}$${\ displaystyle T}$${\ displaystyle T ^ {i}}$${\ displaystyle t_ {i}, t_ {i + 1}, ..., t_ {n}}$${\ displaystyle lcp (s, t)}$${\ displaystyle s}$${\ displaystyle t}$

Az LCP tömb nagyságú tömb , az egyes mezőket a következőképpen definiálva: ${\ displaystyle H}$${\ displaystyle n}$

${\ displaystyle H [i] = {\ begin {cases} {\ text {undefined}}, és {\ text {for}} i = 1 \\ lcp (T ^ {A [i-1]}, T ^ {A [i]}), és {\ text {for}} 2 \ leq i \ leq n \ end {esetek}}}$

Az utótag tömb az összes utótag lexikográfiai rendezését tartalmazza . Informálisabban fogalmazva: az LCP tömb bejegyzése mindig két lexikográfiailag egymás után következő utótagra utal, és leírja a figyelembe vett utótagok leghosszabb közös előtagjának hosszát. A értéke nincs meghatározva, mert a lexikográfiailag legkisebb utótagja van, és nincs elődje. ${\ displaystyle A}$${\ displaystyle T}$${\ displaystyle T}$${\ displaystyle H [1]}$${\ displaystyle T ^ {A [1]}}$${\ displaystyle T}$

példa

Nézd meg a szöveget . ${\ displaystyle T = {\ text {mississippi}} \ $}$

Az utótag tömb a szöveg utótagjainak rendezését jelenti, ahol a megfelelő utótag első betűjének indexét a tömbben tároljuk. A szöveg utótag-rendezése így néz ki: ${\ displaystyle T}$${\ displaystyle T}$

Az LCP tömb két egymást követő utótag leghosszabb közös előtagjának hosszát tartalmazza. Felépíthető úgy, hogy karakterenként követjük össze az utótagok sorrendjében található utótagokat. Például értékének kiszámításához, a képzők kezdve a és összehasonlítjuk egymással: a leghosszabb közös előtagja és az így hossza 2. Ennek megfelelően az . Az LCP tömb fennmaradó értékei ugyanúgy kiszámolhatók. A maradék értéke meghatározatlan marad, mert nincs lexikográfiailag elérhető utótag . A szöveg LCP tömbje így néz ki: ${\ displaystyle H}$${\ displaystyle H [10]}$${\ displaystyle A [10]}$${\ displaystyle A [9]}$${\ displaystyle T ^ {A [10]} = T ^ {4} = {\ text {sissippi}} \ $}$${\ displaystyle T ^ {A [9]} = T ^ {7} = {\ text {sippi}} \ $}$${\ displaystyle {\ text {si}}}$${\ displaystyle H [10] = 2}$${\ displaystyle H [1]}$${\ displaystyle T ^ {A [1]} = T ^ {12} = \ $}$${\ displaystyle T}$

én	1	2	3	4	5.	6.	7.	8.	9.	10.	11.	12.
Szia]	${\ displaystyle \ bot}$	0	1	1	4	0	0	1	0	2	1	3

számítás

Az LCP tömb kiszámításának legegyszerűbb módja az lenne (mint a fenti példában), ha a lexikográfiailag egymás után következő utótagokat karakterenként, az utótag tömb segítségével hasonlítanánk össze, hogy kiszámoljuk a leghosszabb közös előtag hosszát. Legrosszabb esetben azonban ez a módszer futási időt eredményez . Ha például egy szöveg ugyanazokat a karaktereket tartalmazza , összességében összehasonlításokat kell végezni . ${\ displaystyle O (n ^ {2})}$${\ displaystyle n}$${\ displaystyle 1 + 2 + 3 + ... + (n-1) = O (n ^ {2})}$

A hatékonyabb megközelítés az LCP-bejegyzések szöveg szerinti kiszámításának alapgondolatán alapul. Tegyük fel , hogy egymás utáni értékek az utótag tömbben, és közös karakter előtaggal rendelkeznek . Az utótagok , majd közös karakterek vannak. Azonban, és nem kell egymás mellett lenniük az utótag tömbben; könnyen előfordulhatnak olyan utótagok, amelyek lexikográfiailag és között vannak . Tegyük fel , hogy az érték az érték előtt van az utótag tömbben. Akkor és az utótagok lexikográfiai rendezése miatt legalább közös karakterekkel kell rendelkezniük (mert ez az utótag tömb között és benne van ), azaz elegendő lenne összehasonlítani a két képzőt a -edik karakterrel kezdődően . ${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle T ^ {i}}$${\ displaystyle T ^ {j}}$${\ displaystyle h}$${\ displaystyle T ^ {i + 1}}$${\ displaystyle T ^ {j + 1}}$${\ displaystyle h-1}$${\ displaystyle i + 1}$${\ displaystyle j + 1}$${\ displaystyle T ^ {i + 1}}$${\ displaystyle T ^ {j + 1}}$${\ displaystyle k}$${\ displaystyle i + 1}$${\ displaystyle T ^ {i + 1}}$${\ displaystyle T ^ {k}}$${\ displaystyle h-1}$${\ displaystyle k}$${\ displaystyle i + 1}$${\ displaystyle j + 1}$${\ displaystyle h}$

Ehhez a megközelítéshez az inverz utótag tömbre van szükség annak megállapításához, hogy egy adott érték hol található. Ez az inverz permutáció az , hogy jelzi, ha az utótag tömb értéke található. ${\ displaystyle A ^ {- 1}}$${\ displaystyle A}$${\ displaystyle A ^ {- 1}}$${\ displaystyle A}$${\ displaystyle A ^ {- 1} [i]}$${\ displaystyle A}$${\ displaystyle i}$

A következő algoritmus eredményei:

 1LCP-Array(T, A, n)
 2   for (i=1 to n)  {
 3      Ainv[A[i]] = i;
 4   }
 5   H[1] = 0;
 6   h = 0;
 7   for (i=1 to n) {
 8      if (Ainv[i] ≠ 1) {
 9         j = A[Ainv[i] - 1]
10         while T[i+h] = T[j+h]
11            h = h + 1
12         H[Ainv[i]] = h
13         h = max(0, h - 1)
14      }
15   }

A futási idő lineáris, mert a feltételezhető maximum az érték . Mivel minden lépés csak 1-gyel csökken, a belső while ciklus legtöbbször végrehajtásra kerül . Ennek eredménye a teljes futási idő . ${\ displaystyle h}$${\ displaystyle n}$${\ displaystyle h}$${\ displaystyle O (n)}$${\ displaystyle O (n)}$

A fent bemutatott megközelítés Kasai et al. (2001) és ez az első publikált algoritmus, amely lineáris időben számítja ki az LCP tömböt. Manzini (2004) fejlesztett egy továbbfejlesztett verziót, amely nem igényel további memóriát a tényleges szövegen, az utótag tömbön és az LCP tömbön kívül. További fejlesztés a Kärkkäinen, Manzini és Puglisi φ algoritmusa: Míg az eredeti algoritmus gyorsítótárhiányokat okozott a nem hosszú egymás utáni hozzáférés révén a tömbökhöz megfelelő hosszú szövegekhez (mégpedig a 3., 9., 10. és 12. sorban), az φ algoritmus csak cache-hiányokkal kezelhető. ${\ displaystyle 4n}$ ${\ displaystyle 3n}$

A fent említett algoritmusok egy létező utótag tömböt használnak az LCP tömb kiszámításához. Vannak algoritmusok, amelyek az LCP tömböt az utótag tömbjével egyidejűleg kiszámítják. A jelenleg leggyorsabb lineáris algoritmus Fischertől (2011) származik.

Gog & Ohlebusch (2011) két olyan algoritmust tett közzé, amelyeknek a legrosszabb esetben másodfokú futási ideje van, de a gyakorlatban gyorsabbak, mint a fent említett lineáris időalgoritmusok.

Gyorsított szöveges keresés az LCP tömb segítségével

Az utótag tömb segítségével bináris keresés segítségével meghatározható egy hosszúságú minta előfordulása egy hosszú szövegben . Mivel az utótag tömbben található utótagok lexikografikusan vannak rendezve, az összehasonlítások elegendőek ahhoz, hogy megtalálják a lexikológiailag legkisebb (vagy legnagyobb) utótagot, amely tartalmazza. Minden képest legfeljebb karaktert kell hasonlítani, ami azt jelenti, hogy ez a módszer egy futási . ${\ displaystyle P}$${\ displaystyle m}$${\ displaystyle T}$${\ displaystyle n}$${\ displaystyle O (\ log {n})}$${\ displaystyle P}$${\ displaystyle m}$${\ displaystyle O (m \ log {n})}$

Az LCP tömb segítségével a futásidő javítható azáltal, hogy megakadályozzuk, hogy a mintát a bináris keresés minden lépésénél elölről kelljen újra elolvasni. ${\ displaystyle O (m + \ log {n})}$${\ displaystyle P}$

A bináris keresés minden lépésében van egy bal intervallumhatár , egy jobb intervallumkorlát és egy középső elem . Ez összehasonlítva a lexikográfiai utótag (azaz ). Ha mindkét karakterlánc egyezik, akkor a bináris keresés befejeződik, különben a keresést az intervallum bal vagy jobb felében kell folytatni. Megnézzük azt az esetet, amely lexikográfiailag kisebb, mint amennyi - a másik eset hasonló. Legyen a két karakterlánc leghosszabb közös előtagjának hossza. Ez azt jelenti, hogy a -edik karaktere lexikográfiailag kisebb, mint a . ${\ displaystyle l}$${\ displaystyle r}$${\ displaystyle m}$${\ displaystyle P}$${\ displaystyle A [m]}$${\ displaystyle T ^ {A [m]}}$${\ displaystyle P}$${\ displaystyle T ^ {A [m]}}$${\ displaystyle k = lcp (P, T ^ {A [m]})}$${\ displaystyle k + 1}$${\ displaystyle P}$${\ displaystyle T ^ {A [m]}}$

Az új intervallumnak vannak határai és és a középső eleme . Legyen a leghosszabb közös előtag hossza a régi és az új középső elem között. Esetmegkülönböztetés következik: ${\ displaystyle l}$${\ displaystyle m}$${\ displaystyle m '}$${\ displaystyle k '= lcp (T ^ {A [m]}, T ^ {A [m']})}$

• ${\ displaystyle k <k '}$: Az utótagok -edik karaktere és ugyanaz. Ezért lexikográfiai szempontból is kisebbnek kell lennie, és a bináris keresés további összehasonlítás nélkül folytatható az intervallum bal felében.${\ displaystyle k + 1}$${\ displaystyle T ^ {A [m]}}$${\ displaystyle T ^ {A [m ']}}$${\ displaystyle P}$${\ displaystyle T ^ {A [m ']}}$
• ${\ displaystyle k> k '}$: Emiatt az utótag lexikográfiailag kisebb, mint az utótag . Ez azt jelenti, hogy az utótag -th karakterének kisebbnek kell lennie, mint az utótag -th karakterének . Mivel és legalább egy karakterből álló közös előtag van , következik, hogy a lexikográfiai szempontból kisebb, mint P, és a bináris keresést a jobb oldalon folytatjuk.${\ displaystyle m '<m}$${\ displaystyle T ^ {A [m ']}}$${\ displaystyle T ^ {A [m]}}$${\ displaystyle k '+ 1}$${\ displaystyle T ^ {A [m ']}}$${\ displaystyle k '+ 1}$${\ displaystyle T ^ {A [m]}}$${\ displaystyle T ^ {A [m]}}$${\ displaystyle P}$${\ displaystyle k '+ 1}$${\ displaystyle T ^ {A [m ']}}$
• ${\ displaystyle k = k '}$: és legyen legalább karakterből álló közös előtag . Mindkét karakterláncot itt kell összehasonlítani, ahol az összehasonlításnak csak a -edik karakterrel kell kezdődnie .${\ displaystyle P}$${\ displaystyle T ^ {A [m ']}}$${\ displaystyle k}$${\ displaystyle k + 1}$

A leírt módszerrel soha nem szükséges olyan karaktereket olvasni, amelyek már elolvastak a bináris keresésben . A módszer Manber és Myers származik. Mivel az LCP tömb csak a lexikografikusan egymást követő utótagok értékeit tartalmazza , az alábbiakban bemutatjuk, hogyan lehet hatékonyan kiszámítani az értékeket. ${\ displaystyle P}$${\ displaystyle lcp}$${\ displaystyle lcp}$

Általánosságban elmondható, hogy két utótag leghosszabb közös előtagja megtalálható az LCP tömb fölötti Range Minimum Query használatával . Két utótag esetében vegye figyelembe az összes olyan toldalékot, amely lexikográfiailag kettő között van: Ha két egymást követő képzőnek van a leghosszabb közös előtagja , és a lexikográfiai rendezés miatt nem lehet hosszabb közös előtag. Az érték tehát pontosan megfelel az LCP bejegyzések fölötti minimumnak . Ez a minimum állandó idő alatt megtalálható a tartomány minimális lekérdezéseinek megfelelő módszereivel.${\ displaystyle T ^ {A [i]}, T ^ {A [j]}}$${\ displaystyle k}$${\ displaystyle T ^ {A [i]}}$${\ displaystyle T ^ {A [j]}}$${\ displaystyle lcp (T ^ {A [i]}, T ^ {A [j]})}$${\ displaystyle H [i + 1], ..., H [j]}$

irodalom

• Enno Ohlebusch bioinformatikai algoritmusok: szekvenciaelemzés, genom-átrendeződések és filogenetikai rekonstrukció . Oldenbusch Verlag, 2013, 4. fejezet.

Egyéni bizonyíték

1. ↑ ^{a b} Udi Manber, Gene Myers: Utótag tömbök: Új módszer az on-line karakterlánc-keresésekhez . In: SIAM Journal on Computing . 22., 5. szám, 1993, 935. oldal. Doi : 10.1137 / 0222058 .
2. Ai Kasai, T. és mtsai: Linear-Time Longest-Common-Prefix Computation in Suffix . In: A 12. éves szimpózium folytatása a kombinatorikus mintaillesztésről, 2001.
3. ^ Manzini, Giovanni: Két helytakarékos trükk a lineáris idő LCP tömb kiszámításához . In: Előadások a számítástechnikában, 3111. évfolyam, 372. oldal, 2004.
4. ↑ Kärkkäinen, Juha; Manzini, Giovanni; Puglisi, Simon J.: Permuted Longest-Common-Prefix Array . In: Előadási jegyzetek a számítástechnikában, 5577. évfolyam, 181. oldal, 2009.
5. ^ Fischer, Johannes: Az LCP-tömb indukálása . In: Lecture Notes in Computer Science, 6844. évfolyam, 374–385., 2011.
6. ↑ Gog, Simon; Ohlebusch, Enno: Gyors és könnyű LCP-tömb építési algoritmusok . In: Az Algoritmusmérnöki és Kísérleti Műhelymunka anyagai, ALENEX, 2011. 25-34.
7. ^ Fischer, J. és V. Heun: Az RMQ probléma elméleti és gyakorlati fejlesztései, az LCA-hoz és az LCE-hez benyújtott alkalmazásokkal . In: Kombinatorikus mintaillesztés . 2006, 36–48. doi : 10.1007 / 11780441_5 .
8. ^ Fischer, J. és V. Heun: Helytakarékos előfeldolgozási rendszerek a statikus tömbök tartományának minimális lekérdezéséhez . In: SIAM J. Comput. 40 (ápr) . 2011, 465-492. doi : 10.1137 / 090779759 .