[EMAIL PROTECTED] wrote:
> Hi Tony,
> A challenge that cannot pass unnoticed....(:-)
> However, it would help if you gave an example if input and output.
> Does the pattern string involve regular expressions or is it just a verbatim
> string?
> What do you mean by efficient: ordo-wise, or down to concrete micro-seconds?
> --Thomas
>
> Tony writes:
> > Hello All,
> > I'm stumped by a problem that seems to me to be hard to
> > do efficiently in Haskell or any 'pure' functional language. That is,
> > making an inverse index.
> >
> > The particular problem stems from a particularly efficient method of
> > string searching (at least it's efficient as an imperative algorithm)
> > which involves analysing the pattern string to find out the last
> <-------------- should have said 'first'
> > position in the pattern where each letter of the 'alphabet' appears and
> > make an array of such positions indexed on the letters of the alphabet.
> > I just cannot see an efficient way of writing this which doesn't create
> > more than one version of the array. It appears to need to update the
> > array for each occurrence of the letters.
> >
> > Can anyone think of an efficient method. Monads?
> >
> >
> >
Hi Thomas,
Initially, at any rate, I want to deal with simple strings
without bothering about regular expressions. If I can deal with them, the
regular expressions may be an extension. Thus I want a function 'analyse' which
(assuming the 'ordinary' English alphabet of lower case letters as indices) is
such that, for instance,
analyse "abbe" = an array, pos, such that pos ! 'a' == 0, pos ! 'b' ==1, pos !
'e' ==3, and all other pos ! i are -1 (say). [Note my correction to the
specification below]
As the analysis may be done for a great many patterns (the application I have
in mind is gene-sequence searching), it's important that it should be fast
(though luckily only one analysis per pattern is needed, however many strings
we are searching)
--
Tony Davie, Computer Science, St.Andrews University, North Haugh, St.Andrews
Scotland, KY16 9SS, Tel: +44 1334 463257, Fax: +44 1334 463278
mailto:[EMAIL PROTECTED] Home: http://www.dcs.st-and.ac.uk/~ad/Home.html
Handel Index and Chronology:
http://bruichladdich.dcs.st-and.ac.uk/HandelWWW/HandelCat.html
