Home Original page

searching algorithm

Terry Reedy tjreedy at udel.edu
Thu May 10 15:49:18 EDT 2007 
"Neil Cerutti" <horpner at yahoo.com> wrote in message 
news:slrnf46ph1.1hg.horpner at FIAD06.norwich.edu...
| On 2007-05-10, Gigs_ <gigs at hi.t-com.hr> wrote:
| > if user type: "abs" program should list all words above in
| > english and in croatian if user type: "absorb" than program
| > should list last 3 words in english and in croatian
|
| A solution that solves the problem with a data structure might be
| a multi-tree.

Specific computer science terms are prefix tree or trie (from reTRIEval).
http://en.wikipedia.org/wiki/Trie
gives an introduction.

| Each node points at a set of following letters, and a set of
| croatian translations, either of which might be empty, making the
| node a leaf.
|
| For the above (abrideged) dictionary, you would generate (use a
| fixed-width "programmers" font so the tree looks good):
|
|                 a
|                 |
|                 b
|                 |
|                 s
|                / \
|               i   o
|              /   / \
|             n   l   r
|            /   / \   \
|           t   u   v   b->(absorbirati, crpisti)
|          /    |   |
| (pelin)<-h     t   e->(odrije?iti, osloboditi)
|         |     |
| (pelin)<-e     e->(apsolutan, apsolutni kod)
|
| As the user enter letters, you just march down the tree, printing
| all the words held in leaf nodes held in the current node.

tjr
|
More information about the Python-list mailing list