searching algorithm

**=?windows-1252?q?S=E9bastien_Ramage?=** · May 10 '07, 06:05 PM

Re: searching algorithm

I have made a script that search anagram based on the ODS file ( call
OSW in english, Official Scrabble Words)
it load a file that contain 369085 words (one word per line)

I create a dictionnary and store word into using the length of the
word as key
example : mydict[2] contain a list of word with length = 2

first I select the correct dict entry and in a second time I scan this
list searching correct word

my file contains 369085 and it's pretty fast

Seb

**Neil Cerutti** · May 10 '07, 06:35 PM

Re: searching algorithm

On 2007-05-10, Gigs_ <gigs@hi.t-com.hrwrote:

Hi all!
>
I have text file (english-croatian dictionary) with words in it
in alphabetical order. This file contains 179999 words in this
format: english word: croatian word
>
I want to make instant search for my gui Instant search, i mean
that my program search words and show words to user as user
type letters. yes, it needs to be fast
>
Can someone give me some points (approaches) how to make this
Should i make indexes and go with file.seek
>
or should breake dictionary in peaces and put words that start
with a in one and with b in another...
>
So if i have this words
[abridged dictionary below]
absinth:pelin
absinthe:pelin
absolute:apsolu tan
absolute:apsolu tni kod
absolve:odrije? iti
absolve:oslobod iti
absorb:absorbir ati
absorb:apsorbir ati
absorb:crpsti
>
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.

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 "programmer s" 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.

--
Neil Cerutti
We shall reach greater and greater platitudes of achievement. --Richard J.
Daley

**Terry Reedy** · May 10 '07, 07:55 PM

Re: searching algorithm

"Neil Cerutti" <horpner@yahoo. comwrote in message
news:slrnf46ph1 .1hg.horpner@FI AD06.norwich.ed u...
| On 2007-05-10, Gigs_ <gigs@hi.t-com.hrwrote:
| 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).

Trie - Wikipedia

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 "programmer s" 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
|

**Gordon Airporte** · May 10 '07, 08:45 PM

Re: searching algorithm

For the above (abrideged) dictionary, you would generate (use a
fixed-width "programmer s" 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.
>

Call me dense, but how does one do this in Python - which doesn't have
pointers? Dictionaries with dictionaries within dictionaries... (with
each letter as the key and the its children as values) is going to be
extremely space inefficient, right?

**James Stroud** · May 10 '07, 10:05 PM

Re: searching algorithm

Gordon Airporte wrote:

>

>For the above (abrideged) dictionary, you would generate (use a
>fixed-width "programmer s" 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.
>>

>
Call me dense, but how does one do this in Python - which doesn't have
pointers? Dictionaries with dictionaries within dictionaries... (with
each letter as the key and the its children as values) is going to be
extremely space inefficient, right?

How would this be significantly more space inefficient than "pointers"?
The implementation of the dict would, in fact, itself be pointers, where
each key (same memory requirement if using pointers) is mapped to a
pointer to a dict node or a pointer to a leaf, same as with a more "low
level" construction. A printout of the graph as a dict might look a
little ugly, though.

I could be wrong, however.

James

**Neil Cerutti** · May 10 '07, 10:15 PM

Re: searching algorithm

On 2007-05-10, Gordon Airporte <JHoover@fbi.go vwrote:

>

>For the above (abrideged) dictionary, you would generate (use a
>fixed-width "programmer s" 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.

>
Call me dense, but how does one do this in Python - which
doesn't have pointers? Dictionaries with dictionaries within
dictionaries... (with each letter as the key and the its
children as values) is going to be extremely space inefficient,
right?

Unfortunately, I don't know the space tradeoffs in Python
offhand. Lists and tuples make excellent trees.

The above might be stored as follows:

Every node is a tuple of its letter, a list of its children, and
a list of its words. So the two 'pelin' nodes would be (with 'e'
referenced in the 'h' node):

('h', [('e', [], ['pelin'])], ['pelin'])

That would in turn be "stored" in the t, n, i and s nodes.

('s',
[('i',
[('n',
[('t',
[('h', [('e', [], ['pelin'])], ['pelin'])
[])]
[])]
[]), ('o' trie (thanks Terry) omitted for my sanity)])

It's a lot harder to write by hand than it would be to use.

My intuition says it shouldn't be terribly hard on resources for
for a 180K dictionary, but I could be wrong. I'm too lazy to
measure. ;)

If it does turn out to be unreasonably huge, then you'd fall back
on solving the problem completely with a binary search returning
a range (I'm not sure of the name), which would be more expensive
at run time, but might be fast enough, and would use a minimal
amount of 'resources'.

--
Neil Cerutti

**Terry Reedy** · May 11 '07, 03:55 AM

Re: searching algorithm

"Neil Cerutti" <horpner@yahoo. comwrote in message
news:lNM0i.3441 2$G23.27437@new sreading01.news .tds.net...
| Every node is a tuple of its letter, a list of its children, and
| a list of its words. So the two 'pelin' nodes would be (with 'e'
| referenced in the 'h' node):
|
| ('h', [('e', [], ['pelin'])], ['pelin'])
|
| That would in turn be "stored" in the t, n, i and s nodes.
[snip]

At the outer level, I would use a list in order to build the structure in
pieces, one for each letter, and then add them in.

At the top level, the letters do not need explicit storage. The first
subtree is for words starting with 'a', etc. In other words, the position
of each subtree indicates its starting letter. For most letters, this can
be carried on another level.

tjr

**ciju** · May 11 '07, 05:35 AM

Re: searching algorithm

On May 11, 3:12 am, Neil Cerutti <horp...@yahoo. comwrote:

On 2007-05-10, Gordon Airporte <JHoo...@fbi.go vwrote:
>
>
>
>
>

For the above (abrideged) dictionary, you would generate (use a
fixed-width "programmer s" font so the tree looks good):

>

>

As the user enter letters, you just march down the tree, printing
all the words held in leaf nodes held in the current node.

>

Call me dense, but how does one do this in Python - which
doesn't have pointers? Dictionaries with dictionaries within
dictionaries... (with each letter as the key and the its
children as values) is going to be extremely space inefficient,
right?

>
Unfortunately, I don't know the space tradeoffs in Python
offhand. Lists and tuples make excellent trees.
>
The above might be stored as follows:
>
Every node is a tuple of its letter, a list of its children, and
a list of its words. So the two 'pelin' nodes would be (with 'e'
referenced in the 'h' node):
>
('h', [('e', [], ['pelin'])], ['pelin'])
>
That would in turn be "stored" in the t, n, i and s nodes.
>
('s',
[('i',
[('n',
[('t',
[('h', [('e', [], ['pelin'])], ['pelin'])
[])]
[])]
[]), ('o' trie (thanks Terry) omitted for my sanity)])
>
It's a lot harder to write by hand than it would be to use.
>
My intuition says it shouldn't be terribly hard on resources for
for a 180K dictionary, but I could be wrong. I'm too lazy to
measure. ;)
>
If it does turn out to be unreasonably huge, then you'd fall back
on solving the problem completely with a binary search returning
a range (I'm not sure of the name), which would be more expensive
at run time, but might be fast enough, and would use a minimal
amount of 'resources'.
>
--
Neil Cerutti

The problem that I see here is that each time user types a letter, all
the leaf nodes in the subtree would have to be traversed again. This
computation was already done for all the letters user typed before the
last one.

My suggestion would be to have two data structures. The first one
similar to the tree mentioned above, but leaf nodes need not have
Croatian translations, and each node should also have total number of
leafs in both left siblings and right siblings of that node. The
second data structure would be list of English:Croatia n word pairs.

As the user types a new letter, we just have to remove(not show), the
number of leaf elements in the left and/or right siblings, from left
and/or right of the second data structure. So we just have to keep
track of the node we r currently at(in the tree) and the start, end
index for the second data structure(basic ally the list to be shown to
the user).

By the way, both data structures could be implemented as tuple in
python, for I suppose, if only lookup is needed tuple gives better
performance than list.

ciju

**Michael Bentley** · May 11 '07, 08:55 AM

Re: searching algorithm

On May 10, 2007, at 12:26 PM, Gigs_ wrote:

Hi all!
>
I have text file (english-croatian dictionary) with words in it in
alphabetical
order.
This file contains 179999 words in this format:
english word: croatian word
>
I want to make instant search for my gui
Instant search, i mean that my program search words and show words
to user as
user type letters.
yes, it needs to be fast
>
Can someone give me some points (approaches) how to make this
Should i make indexes and go with file.seek
>
or should breake dictionary in peaces and put words that start with
a in one and
with b in another...
?????
>
So if i have this words
...
>
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
>
>
>
>
>
any help would be appreciate!
my apologies for bad english

Here's an idea: use a rats' nest of dictionaries and do all the
lookup work up front when you build the rats' nest. Maybe something
like this:

#! /usr/bin/env python
import pprint

dictionary = """absinth:peli n
absinthe:pelin
absolute:apsolu tan
absolute:apsolu tni kod
absolute:apsolu tno
absolute:čist
absolute:nesumn jiv
absolute:potpun
absolute:savrse n
absolute coordinates:aps olutne koordinate
absolute frequency:apsol utna učestalost
absolute gap:apsolutni jaz
absolute line spacing:apsolut ni međurazmak linija
absolute majority:apsolu tna većina
absolute pointing device:apsolutn i pokazivački uređaj
absolute quantity:apsolu tni udio
absolute value:apsolutna vrijednost
absolute zero:apsolutna nula
absolutely:apso lutno
absolutely:bezu vjetno
absolutely:neza visno
absolutely:potp uno
absolutely:samo stalno
absolutely:sasv im
absolution:odrj esenje
absolution:opro staj
absolutism:apso lutizam
absolve:odrijes iti
absolve:oslobod iti
absorb:absorbir ati
absorb:apsorbir ati
absorb:crpsti"" "

lookup = {'words':{}, 'letters':{}}

for translation in dictionary.spli t('\n'):
english, croatian = translation.spl it(':')
if english in lookup['words']:
lookup['words'][english].append(croatia n)
else:
lookup['words'][english] = [croatian]

for position, letter in enumerate(engli sh):
if position == 0:
youAreHere = lookup['letters']

if letter not in youAreHere:
youAreHere[letter] = {'words':[]}
youAreHere[letter]['words'].append(lookup['words'][english])
youAreHere = youAreHere[letter]

def tryit(partial):
youAreHere = lookup['letters']
for letter in partial:
youAreHere = youAreHere[letter]
return youAreHere['words']

if __name__ == '__main__':
pprint.pprint(t ryit('abso'))

Hope this helps,
Michael
---
The Rules of Optimization are simple.
Rule 1: Don't do it.
Rule 2 (for experts only): Don't do it yet.
-- Michael A. Jackson , "Principles of
Program Design", 1975.

**Michael Bentley** · May 11 '07, 09:15 AM

Re: searching algorithm

>

Call me dense, but how does one do this in Python - which doesn't have
pointers? Dictionaries with dictionaries within dictionaries... (with
each letter as the key and the its children as values) is going to be
extremely space inefficient, right?

Isn't *everything* in python essentially a pointer? Dictionaries
with dictionaries within dictionaries... My gut feeling (which means
I have not measured it, so I don't actually know) is that it would
not be space inefficient. Perhaps someone who knows more about this
will speak up?

**Neil Cerutti** · May 11 '07, 01:25 PM

Re: searching algorithm

On 2007-05-11, ciju <mail.ciju.cher ian@gmail.comwr ote:

By the way, both data structures could be implemented as tuple
in python, for I suppose, if only lookup is needed tuple gives
better performance than list.

I used a list instead of a tuple where I thought a list would be
convenient while building the data structure. But you could
convert everything to tuples in the end, it's true.

--
Neil Cerutti

**Alex Martelli** · May 11 '07, 02:35 PM

Re: searching algorithm

Michael Bentley <michael@jedimi ndworks.comwrot e:

Call me dense, but how does one do this in Python - which doesn't have
pointers? Dictionaries with dictionaries within dictionaries... (with
each letter as the key and the its children as values) is going to be
extremely space inefficient, right?

>
Isn't *everything* in python essentially a pointer? Dictionaries
with dictionaries within dictionaries... My gut feeling (which means
I have not measured it, so I don't actually know) is that it would
not be space inefficient. Perhaps someone who knows more about this
will speak up?

Dicts are hash tables, and therefore, for performance, always keep some
"extra" space (so that the table won't be too full).

Alex

**Michael Bentley** · May 12 '07, 05:25 AM

Re: searching algorithm

On May 11, 2007, at 3:50 AM, Michael Bentley wrote:

>
Here's an idea: use a rats' nest of dictionaries and do all the
lookup work up front when you build the rats' nest. Maybe something
like this:

....

Oops! This is better :-)

#! /usr/bin/env python
import pprint

dictionary = """absinth:peli n
absinthe:pelin
absolute:apsolu tan
absolute:apsolu tni kod
absolute:apsolu tno
absolute:čist
absolute:nesumn jiv
absolute:potpun
absolute:savrse n
absolute coordinates:aps olutne koordinate
absolute frequency:apsol utna učestalost
absolute gap:apsolutni jaz
absolute line spacing:apsolut ni međurazmak linija
absolute majority:apsolu tna većina
absolute pointing device:apsolutn i pokazivački uređaj
absolute quantity:apsolu tni udio
absolute value:apsolutna vrijednost
absolute zero:apsolutna nula
absolutely:apso lutno
absolutely:bezu vjetno
absolutely:neza visno
absolutely:potp uno
absolutely:samo stalno
absolutely:sasv im
absolution:odrj esenje
absolution:opro staj
absolutism:apso lutizam
absolve:odrijes iti
absolve:oslobod iti
absorb:absorbir ati
absorb:apsorbir ati
absorb:crpsti"" "

lookup = {'words':{}, 'letters':{}}

for translation in dictionary.spli t('\n'):
english, croatian = translation.spl it(':')
if english in lookup['words']:
lookup['words'][english].append(croatia n)
else:
lookup['words'][english] = [english, croatian]

for position, letter in enumerate(engli sh):
if position == 0:
youAreHere = lookup['letters']

if letter not in youAreHere:
youAreHere[letter] = {'words':[]}

if lookup['words'][english] not in youAreHere[letter]['words']:
youAreHere[letter]['words'].append(lookup['words'][english])
youAreHere = youAreHere[letter]

def tryit(partial):
youAreHere = lookup['letters']
for letter in partial:
youAreHere = youAreHere[letter]
return youAreHere['words']

if __name__ == '__main__':
pprint.pprint(t ryit('abs'))
print '=' * 50
pprint.pprint(t ryit('absorb'))

**aaronwmail-usenet@yahoo.com** · May 12 '07, 06:05 PM

Re: searching algorithm

On May 10, 1:26 pm, Gigs_ <g...@hi.t-com.hrwrote:

Hi all!
>
I have text file (english-croatian dictionary) with words in it in alphabetical
order.
This file contains 179999 words in this format:
english word: croatian word

Let's assume it's okay to have all the data in memory.
In my experience the very fastest way to do what you
want is to store the strings in a sorted list and use
the binary search library module bisect. I once compared this
with doing something similar with tries and it was
much faster. It's also the most simple way to do it, which
is nice too :).
-- Aaron Watters

===
never eat anything bigger than your head -- kliban

searching algorithm

searching algorithm

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment