On Wed, Feb 04, 2009 at 08:51:26AM +0100, Hofmann Johannes wrote:
On Tue, Feb 03, 2009 at 11:54:56PM +0000, Jo?o Ricardo Louren?o wrote:
Ter, 2009-02-03 ?s 21:39 +0100, Hofmann Johannes escreveu:
Hello,
On Tue, Feb 03, 2009 at 07:48:18PM +0000, Jo?o Ricardo Louren?o wrote:
Greetings.
I 'spotted' a TODO on searching 'backwards' and decided to have a go at it.
Great.
Basically, I implemented the Search Previous feature.
I must say I have difficulties understanding the code behind FindtextState::search0(), so I did not base my code on it at all. Sure it could possibly be optimized, but it seems to do the job for now, I haven't found any bugs, if you find any, please do say.
FindtextState implements the Knuth-Morris-Pratt algorithm http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm for efficient searching. It is pretty clever but a bit tricky. I see some issues in your implementation. E.g. try to search for 'ab' in a string 'abababa'. Even more tricky is searching for ababb in abababb, i.e. the prefix matches, but once it no longer does you would need to backtrack. The easiest but inefficient way to implement searching is doing a strcmp() at every text position. The Knuth-Morris-Pratt algorithm avoids that. I think it would be best to adapt search0 somehow to allow backward searching - it's more or less the same thing as forward searching anyway. Some ugly edge cases when switching between forward and backward maybe :-)
Thanks for working on that, Johannes
Additionally, I did not set any hotkeys for the search-previous action, maybe something like SHIFT+RETURN, since RETURN handles searching forwards?
Also, I did not add any tests, and I only altered a line to make them compilable, but I might add some tests soon.
Thanks,
Jo?o
Thanks for your answer.
OK, I am still trying to 'go deep' with the KMP algorithm, but I have got (provisory) working search0Backwards() replacement. How efficient do you think it is to handle the word by reversing it? Rephrasing that, do you think there is a 'really' better way of searching backwards, than reversing the word and searching backwards? As far as code-changes it takes very few lines and I have a working example of it. However, the extra reversing work might hit us hard.
Reversing the word (needle) we are searching for is no problem. It's supposed to be rather small and we only need to reverse it once. The point is to avoid the backtracking. So that every letter in the text (haystack) is only visited once.
If reversing the needle is all it takes, go ahead. If the code is simple and it takes twice the time a forward search, go ahead too. Backward search is much less used than forward search and it's better to have it than not, and unless the delay is annoying there's no compelling need to optimize. -- Cheers Jorge.-