Javított mondatellenőrzés a LibreOffice-ban (és egy érdekes CPython probléma)

LibreOffice, OpenOffice.org

A LibreOffice magyar mondatellenőrzőjének elkészült az 1.5-ös javító kiadása. A javítás a LibreOffice 4.2 december 20-án megjelent RC1 előzetes kiadásában is helyett kapott, de külön is telepíthető a fenti kiterjesztéssel. Egy újdonság, a szóközökkel „r i t k í t o t t” szavakra adott cserejavaslat mellett javítja a mondatellenőrzés potenciális „lefagyását” is.

A javított probléma rávilágít a CPython „re” programkönyvtárának érdekes tulajdonságára: bizonyos egyszerű szabályos kifejezések képesek lefagyasztani a CPythont, azon keresztül pedig az azt használó, itt a Lightproof mondatellenőrző komponenst is. Annyiban meglepő ez, hogy hasonló lefagyást az optimalizált Unix/Linux regexp könyvtárak nem produkálnak, így érdemes erre is figyelni a (C)Python fejlesztőknek (l. bővebben a LibreOffice-hibajegyben és a LibreOffice.hu-hírben).

( zozi56 | 2013. 12. 26., cs – 18:02 )

A regexes problémának az az oka, hogy a CPython visszalépéses kereséssel implementálja a mintaillesztést (Thompson-féle) véges determinisztikus automata helyett, így bizonyos inputokra O(2n) lesz a futásidő (n az inputhossz), szemben a másik megoldás O(m×n)-jével (m a mintahossz).

Igen, de (lineáris időben) minimalizálható lineárisan sok állapotúra.

Back reference-t valóban nem tud (mivel akkor ugye a kifejezés már nem harmadik típusú), minden mást azt hiszem, igen. Érdekes lenne egy olyan implementáció, ami a kifejezés struktúrájától függően választana illesztési algoritmust. Nem néztem utána, van-e már ilyen.