Re: Do java support 'String' methods properly ?

Hi,

Googmeister wrote: 
This is how Java implements indexOf() as well. It is efficient (linear)
for "typical" inputs, but has a quadratic worst case.


Depends on what is 'typical' for you. :-)

(BTW, linear search is not really quadratic, but M*N.)

Google for Knuth-Morris-Pratt and Boyer-Moore-Horspool for *efficient*
String searching algorithms!


Anyone know why Java's indexOf doesn't use Boyer-Moore
(sublinear on typical inputs) for long strings? I suspect it's a
combination of requiring extra space proportional to the alphabet
size and difficulties in dealing with the subtleties of Unicode
(e.g., code points). But it would be nice to hear from the experts.

IIRC, all algorithms (linear, BMH, KMP) have different advantages, depending on the sizes of the text and the pattern, the size of the alphabet, the distribution of the characters and if you are searching a pattern in different texts (do not forget that you need to generate a "suffix-list" for the pattern)!

If the both the text and the pattern are very short (perhaps only 10 to 20 chars?), it is obvious that linear search ist the best. If the alphabet is very short (eg only A and B), the pattern might be AAAAA, so that KMP (*) has no advantage over linear search as well.

Fact is: You simply cannot decide which algorithm is 'best' if you do not know *anything* about the application (which of course sun can't).

And if you want to implement a large text-database or a gene-sequencer, it is obvious that you have to think *a lot* about searching-algorithms, so that *no* implementation (that has not been optimized especially for the exact application (**)) is perfect.

Ciao,
Ingo

(*) It has been nearly 10 years since I implemented these algorithms, and I remember there were some slight differences between BM and BMH wich I do not remember right now. So, forgive me, if I confuse the algorithms...

(**) In these cases, it might often be useful if you do not have the whole text in RAM, but e.g. to have a linked list of "chunks" of texts, with one chunk perhaps of the size of some MB. The rest remains on disk. No default-implementation can deal with that!

.

Relevant Pages

  • RE: Find text in Word - without affecting the Find dialog box
    ... how to efficiently find a string in Word plain ... please refer to the String searching algorithms introduced in page: ... serveral commonly used algorithms. ...
    (microsoft.public.office.developer.com.add_ins)
  • Re: Similarity searching
    ... a factor of N*log, if the arrays are big you won't in general have to compare to the last element so I don't see the factor of L**2, and I don't see where that C**2 factor is coming from at all. ... There are also sorting algorithms which don't compare each item to every other item, yet still generate a sorted result. ... Similarity searching is still an active science, but there are a lot of useful algorithms out there now. ...
    (comp.lang.fortran)
  • Re: I need some guideance regarding parallel processing
    ... searching, range searching, associative searching and all the other ... getting good algorithms before you try to optimize things. ... What standard have you implemented to network machines together? ... What message passing standard do you use? ...
    (comp.lang.fortran)
  • Re: Book-able view of ID as speculative science
    ... > is called "Pattern Recognition" by Theodoridis and Koutroumbas, ... > method of searching for something and have a good definition of what ... characteristics of massive amounts of genomic sequences currently ... Map (SOM), is an effective tool for clustering and visualizing ...
    (talk.origins)
  • Merging in parallel computation
    ... We are a research group working on classic algorithms on PRAM. ... the dominant papers on merging, sorting and searching in parallel is ... %T Searching, Merging, and Sorting in Parallel Computation ...
    (comp.parallel)