Qui, 2009-02-05 ?s 20:56 +0000, Jo?o Ricardo Louren?o escreveu:
Qua, 2009-02-04 ?s 10:35 -0300, Jorge Arellano Cid escreveu:
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.
Thanks for the answer.
OK, I think I worked it out, but the string is being reversed everytime we search backwards, to maintain compatibility with forward searching. Of course an alternative is to store it as private member, what do you think?
I couldn't find any function for reversing a C-String in dillo's code, so I put my own as a static member in FindtextState, should I move it elsewhere?
I tested multiple cases and it seems (to me) that this one is bugless, maybe you'll find a nasty/dirty bug I caused, but time will tell :)
Also, the reverse string function was the only one added, all the rest was only altered.
Thanks for the support,
Jo?o
(Apart from the fact I didn't attach any patch...) Scratch that, my bad, that patch contained various bugs. The first kind of bug related to a typo which I now fixed. The second kind because of me interpreting code the wrong way and the third one because of the particular case of searching for things either at the beggining or at the end of the page. I think I fixed all of them and have an updated patch, excuse me for my previous mistakes... Jo?o