Re: Building a Trie

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:  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