A Sequitur algoritmus (vagy Neville-Manning algoritmus ) egy rekurzív algoritmus, amelyet Craig Neville-Manning és Ian Witten fejlesztett ki 1997-ben [1] . Az algoritmus hierarchikus struktúrát ( kontextusmentes nyelvtan ) hoz létre különálló karakterek sorozatából. Az algoritmus lineáris térben, lineáris időben működik. Adattömörítési alkalmazásokban használható [ 2] .
A Sequitur algoritmus úgy építi fel a nyelvtant, hogy egy új szabállyal helyettesíti az ismétlődő kifejezéseket egy adott szekvenciában, és így röviden ábrázolja a sorozatot. Például, ha a sorrend az
S→abcab,az algoritmus megadja
S→AcA, A→ab.Amikor egy bemeneti karakterláncot nézünk, az algoritmus két szabályt követ a hatékony nyelvtani generálás érdekében: egy karakterpár egyediségét és a szabály használatát .
Ha új karaktert választunk ki a sorozatból, az hozzáadódik az utoljára kiválasztott karakterhez, és új karakterpár jön létre . Ha egy ilyen pár korábban létrejött, akkor a rendszer egy új szabályt generál, amely a karakterpárok mindkét előfordulását helyettesíti.
Ez biztosítja, hogy a pár legfeljebb egyszer forduljon elő a nyelvtanban. Például az S→abaaba sorozatban az első négy karakter megtekintése után ab, ba, aa párok jönnek létre . Az ötödik karakter kiválasztásakor az új „ab” pár már létrejött. Ezért az 'ab' mindkét párját S -ben egy új szabállyal (mondjuk A-val) helyettesítjük. Most a nyelvtan S→AaAa, A→ab lesz, és a folyamat addig folytatódik, amíg nem marad ismétlődő pár.
Ez a korlátozás biztosítja, hogy minden szabályt többször használjon a nyelvtan megfelelő részeiben. Vagyis ha egy szabály csak egyszer fordul elő, akkor azt ki kell venni a nyelvtanból, és végre kell hajtani a megfelelő behelyettesítést. Például a fenti példában, ha megkeresi az utolsó karaktert, és alkalmazza az 'Aa' egyediségi szabályt, akkor a nyelvtan S→BB, A→ab, B→Aa karaktereket eredményez . Most az 'A' szabály csak egyszer fordul elő a B→Aa -ban . Tehát A eltávolításra kerül, és végül a nyelvtan S→BB, B→aba lesz .
Ez a korlátozás lehetővé teszi a szabályok számának csökkentését a nyelvtanban.
Az algoritmus úgy működik, hogy megvizsgálja a terminál karakterek sorrendjét, és listát készít az összes beolvasott karakterpárról. Amikor a pár másodszor is előfordul, mindkét pár helyére a létrehozott nem terminális karakter kerül, a karakterpárok listája frissül, hogy megfeleljen az új sorozatnak, és a böngészés folytatódik. Ha a nem-terminális szimbólumpárok csak az újonnan létrehozott szimbólumdefinícióban fordulnak elő, akkor a szimbólum helyébe a definíciója kerül, és törlődik a nem terminális szimbólumok listájáról. Amikor a vizsgálat befejeződött, az átalakított sorozat az eredeti sorozat nyelvtanának legfelső szintű szabályaként értelmezhető. A nem terminális szimbólumok szabálydefiníciói a párok listájában találhatók. Ezek a szabálydefiníciók maguk is tartalmazhatnak további nem terminális szimbólumokat, amelyek definíciói ugyanabban a párlistában találhatók [3] .
| Tömörítési módszerek | |||||||
|---|---|---|---|---|---|---|---|
| Elmélet |
| ||||||
| Veszteségmentes |
| ||||||
| Hang |
| ||||||
| Képek |
| ||||||
| Videó |
| ||||||