[Poppler-bugs] [Bug 8821] Performance Improvement for TextPage:findText()

[bugzilla-daemon at freedesktop.org]

https://bugs.freedesktop.org/show_bug.cgi?id=8821

--- Comment #10 from Johannes Buchner <buchner.johannes at gmx.at> 2010-06-13 23:45:34 PDT ---
Created an attachment (id=36255)
 View: https://bugs.freedesktop.org/attachment.cgi?id=36255
 Review: https://bugs.freedesktop.org/review?bug=8821&attachment=36255

Implementation of KMP (Knuth-Morris-Pratt search algorithm)

I implemented the Knuth-Morris-Pratt algorithm.

As far as I see it works correctly. I tested with the glib-demo tool. But I
didn't test backward search, although I implemented it (simply by reversing
array access indices).

I was able to see about twice the speed in some corner cases, but usually it
has no gain. However, in no case I saw a degradation.

Please review and test!

It should also be considered that we rebuild the search string (Unicode
conversion) and the next-array for KMP on every call of TextPage::findText.
Since it is normally called through all pages, one could save some calculation
there.

I also looked at Boyer-Moore, but it seems stupid to make a lookup table that
covers the whole Unicode space, and implementing it over a list or hashmap
pretty much takes away the benefit of BM.

-- 
Configure bugmail: https://bugs.freedesktop.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.