Newsgroup: it.comp.lang.c++
Titolo: Algoritm for dictionary

Hi
I need help.
My professor told me to find a way to organize a dictionary of about 60k
words.
In other words, i need to find a good way to develop a collection of words,
easy to find, and possibly quick to search.
I am running low of ideas. Can anyone help?
Please answer by mail because i do not read news groups frequently.
Thanx
Willy.
ps: sono italiano....

...


 ps: sono italiano....
 Visti i requisiti di memoria (piuttosto bassi) puoi usare una tavola hash - per delle buone
performance su 60K di dati una tavola grossa anche quattro volte tanto sta tranquillamente
in memoria.
Ora, una buona implementazione e' quella di STL, ma sicuramente ne esistono anche in
pascal o visual basic. Tieni presente che, se i dati fossero realmente parecchi, avresti
bisogno di un buon database, magari dedicato.
Saluti,
    CS
--
Cristiano Sadun - Software Engineering and Consulting
***********Remove NOSPAM from address to reply***********
*********************************************************
"God is Real - unless declared Integer"

 ps: sono italiano....
 Visti i requisiti di memoria (piuttosto bassi) puoi usare una tavola hash - per delle buone
performance su 60K di dati una tavola grossa anche quattro volte tanto sta tranquillamente
in memoria.
Ora, una buona implementazione ic C++ e' quella di STL, ma sicuramente ne esistono


Please answer by mail because i do not read news groups frequently.
The method will depend on the dictionary structure and filling method.
For example, if the dictionary is given "as is" and must only be READ,
then a very complex sort & index, done only once, will pay if it saves
a considerable time in the search process.
You could take into account for example the building of a 26-leaf tree
where every letter determines the next link:
typedef struct tag_TS
{
	struct tag_TS next[26];
	int valid;
} TS;
TS *base[26];
So you start with word="amore":
base[word[0]-'a']->next[word[1]-'a']->next...
and you find valid=1 at the "o", thus indicating that "amo" is a valid
word. You still have "re" and continue checking... "e" too has valid=1
and so you know, that "amore" is in the dictionary. The 'x'-th pointer
of that 'e' is NULL, so you would know that "amorex" is not valid.
Supposing you have 5000 four-letter words, 15000 five-letter and 40000
six-letter, you'll end up with: about 20000 nodes for the first block,
which is mostly full; perhaps other 95000 nodes for the other words.
Each pointer is a dword, so you get about half a megabyte of space. 60
kwords of average 5 letters will get you 300 kb, so that's about it.
The interesting part is that, to check a six letter word you only do 6
checks. Less than that if the word starts with an impossible sequence,
for example "ctrame" will get chucked out when the "r" is met.
Depending on the language (and platform) the whole dictionary might be
kept in memory.
Of course, INPUTING the dictionary into this abysmal "tree" would be a
royal pain in the ass.
Leonardo
".signature": bad command or file name

ps: sono italiano....
Ah, ma allora ti rispondo in italiano, anche se forse parlo meglio
inglese ;)
Cmq, la via più furba è quella di usare un array di 26 puntatori -uno
per lettera dell'alfabeto- che puntano ognuno ad un albero binario di
ricerca -bilanciato se sei in grado di farlo, ma è difficile-.
Per il salvataggio ti conviene usare l'algoritmo
radice-ramosinistro-ramodestro altrimenti ti si sbilancia
completamente quando lo carichi la volta dopo. Se invece lo fai
bilanciato -complimenti, io c'ho messo molto tempo a trovare tutti i
casi particolari- non hai problemi con nessun tipo di visita.
Cordialmente,
Gianni Rondinini, programmer and designer at Pierre s.n.c.
e-mail: mailto:
pie...@mail.asianet.it
homepage: 
http://www.geocities.com/Eureka/Plaza/7153
Red Hat Linux user since 9/25/97
Windows NT Server user since 9/19/97
e-mail: mailto:
pie...@mail.asianet.it