Subject: Re: [xsl] Building a Trie From: "Dimitre Novatchev dnovatchev@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> Date: Thu, 22 Jun 2023 19:38:32 -0000 |
On a first read, it seems that using a suffix tree could be useful for such kind of problems: https://en.wikipedia.org/wiki/Suffix_tree Thanks, Dimitre On Thu, Jun 22, 2023 at 4:34b/AM Michael Mueller-Hillebrand michael.mueller-hillebrand@xxxxxxxxx < xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote: > Well, putting 5 minutes DemoJam in a mail... > > The "problem" I challenged myself with, was the solution to a puzzle > presented in a magazine: Find the longest word in a 16x16 square of > (seemingly random) letters. (This is more fun in German than in English.) > To solve this, I got myself a word list of possible solution words (from a > Wikipedia word list, in case you are interested: > https://wortschatz.uni-leipzig.de/de/download/English). > Next, I created a recursive XSLT function that was started for each square > and crawled from each start letter to the next four candidates (top, right, > bottom, left square) and so on, always comparing the growing substrings > against the list of words. > > And that last step is (in every programming language) expensive if done > like this: $words[starts-with(., $start)] > For my personal satisfaction, I am looking for a better way, and a prefix > index (Trie) seemed to be a good fit. > > Best regards, > - Michael > > > -----Original Message----- > From: Norm Tovey-Walsh ndw@xxxxxxxxxx < > xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> > Sent: Thursday, June 22, 2023 8:53 AM > To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx > Subject: Re: [xsl] Building a Trie > > > Now I learned about Tries https://en.wikipedia.org/wiki/Trie which is > > possibly a helpful method to tackle the left-over problem with my > > DemoJam contribution at Markup UK (thanks a lot for the applause!). > > I expect only a small minority of readers on this list were able to see > your demo jam presentation. Could you give us a quick explanation of the > problem youbre trying to solve? > > Be seeing you, > norm > > -- > Norm Tovey-Walsh <ndw@xxxxxxxxxx> > https://norm.tovey-walsh.com/ > > > A man must have grown old and lived long in order to see how short > > life is.--Schopenhauer
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Building a Trie, Michael Mueller-Hill | Thread | Re: [xsl] Building a Trie, Michael Kay mike@xxx |
Re: [xsl] Building a Trie, Michael Mueller-Hill | Date | Re: [xsl] Grouping elements that ha, Matthieu Ricaud-Duss |
Month |