| Zobrazit předchozí téma :: Zobrazit následující téma |
| Autor |
Zpráva |
majkl
Založen: 28. 08. 2007
Příspěvky: 4
|
 Zaslal: 21. říjen 2010, 17:23:54 Předmět: "Slovnikove" vyhledavani |
 |
|
Zdar vsichni,
mam mozna trochu trapny dotaz, ale prosim neodkazujte mne na google, protoze dle ruznych diskuzi se stalo nemohu rozhodnout:
Potrebuji implementovat nasledujici: Mam nejakou tabulku, ktera obsahuje 4 sloupecky s hodnotami(trochu to zjednodusuji, doopravdy je pocet sloupcu se ruzni, ale znam ho ve chvili kdy data nacitam ze souboru). Ani jeden ze sloupcu nelze pouzit jako klic(tj. hodnoty se mohou ruzne opakovat):
Napr:
| kód: |
aa bb cc dd
aa bc cc ee
aab bbc bc ded
aa bb bb dd
...
|
Hodnoty samotne jsou ruzne dlouhe retezce(v podstate slovnik, ale s vice sloupecky, ktery neobsahuje pouze definici jednoduchych slov, ale obecne celych vet)
A ted potrebuju v tehle tabulce rychle vyhledavat, s tim ze z znam cast hodnot jednotlivych hodnot:
znam
(- znamena ze neni definovano - tudiz vse)
a tohle mi matchne 1, 3 a 4 sloupec.
Potreboval bych vedet, jestli jste neco takoveho resili a co k tomu pouzit? Je lepsi napsat naky vlastni vyhledavaci algoritmus(hashovaci tabulky/stromy/neco special?)? Nebo bude lepsi pouzit nejaky jednoduchy databazovy system?(pokud tu databazi, co byste doporucili? Hlavne je neco co nejjednodussiho, hlavne ne nakou MySQL, nebo jeste neco horsiho, idealne cely db system zakompilovatelny do jednoho exace, popripade s jedinou prilozenou libkou) Hlavni duraz je na rychlost.
Velikost tabulky je max 100 000 zaznamu(no max o par tis. vic, nicmene vetsinou sloupecky obsahuji relativne kratke nekolika znakove retezce(zadne pulstrankove souveti)).
Diky |
|
| Návrat nahoru |
|
 |
micky
Založen: 28. 02. 2008
Příspěvky: 348
Bydliště: Plzeň, Praha
|
| Zaslal: 21. říjen 2010, 18:36:05 Předmět: |
|
|
Hoj,
zkusím několik nápadů, třeba se trefím
1)
| citace: |
| ani jeden ze sloupcu nelze pouzit jako klic |
- jako klíč by se dalo použít číslo řádku v souboru, to je na 100% unikátní, otázkou je, jestli klíč vůbec potřebuješ.
2) Pokud by byly údaje seřazené, pak už by šlo vyhledávat celkem dobře půlením intervalu. ... logN složitost není úplně špatná.
3) Odvážnější myšlenka: Každý sloupec používá hash mapu, která uchovává pro konkrétní řetězec čísla všech řádků, na kterých se vyskytuje. Když zkombinuji ty čísla od každého sloupce, získám kýžené řádky/řádek.
Já bych asi půlil interval, 100000 není zas tak obrovské číslo. Jinak rovnou napsaný framework neznám. Půlení a qsort je otázka půl hodiny. 
_________________
https://www.bluepulsar.cz/
https://twitter.com/11thDream_Game/ |
|
| Návrat nahoru |
|
|
perry
Založen: 28. 07. 2009
Příspěvky: 879
|
| Zaslal: 21. říjen 2010, 19:02:18 Předmět: |
|
|
Kdysi jsem použil na * hledání Ternární Strom (TernaryTree). Pokud bys potřeboval zachovat pozice v "matici", tak by stačilo třeba do listů uložit spolu se stringem pozici [i,j] (u Ternary Tree to teda není takhle triviální, ale upravit to na to jde)
Nevýhoda je, že ten strom žere více paměti (ale zase umí právě * hledání, popř. hledat překlepy ve slovech, takže je to částečně vyváženo). Vyhledávání je potom jako u Binárního Stromu.
_________________
Perry.cz |
|
| Návrat nahoru |
|
|
rezna
Založen: 27. 07. 2007
Příspěvky: 2156
|
| Zaslal: 21. říjen 2010, 19:07:10 Předmět: |
|
|
| na slovnikovy vyhledavani se hodi nejlepe prefixove a postfixove stromy - je ale potreba abychom hledali podle zacatku nebo konce slova |
|
| Návrat nahoru |
|
|
perry
Založen: 28. 07. 2009
Příspěvky: 879
|
| Zaslal: 21. říjen 2010, 19:23:45 Předmět: |
|
|
| citace: |
na slovnikovy vyhledavani se hodi nejlepe prefixove a postfixove stromy - je ale potreba abychom hledali podle zacatku nebo konce slova
|
Tenhle problém právě TernaryTree nemá vzhledem k možnosti hledat **aa**.
_________________
Perry.cz |
|
| Návrat nahoru |
|
|
majkl
Založen: 28. 08. 2007
Příspěvky: 4
|
| Zaslal: 22. říjen 2010, 14:29:01 Předmět: |
|
|
Zdar,
dik vsem,
co se tyce toho klice, to je mi jasne, to ani nevim proc jsem zminil
Ale ted zbytek - vsechny zpusoby rucniho razeni znamenaji razeni podle jednoho klice, ale ja potrebuji vyhledavat pomoci vic sloupecku - to by znamenalo udelat 4(dle meho prikladu) vyhledavaci stromy a udelat prunik mnozin jednotlivych hledani. Totez pro puleni intervalu... nebo ne?
ty stromy budou samy o sobe dost velke, a udelat jeste tech stromu N.. je dost drsny...ale zrejme to jinak a lepe asi nepujde, ze? Jak vubec mivaji udelane vyhledavani databaze? |
|
| Návrat nahoru |
|
|
rezna
Založen: 27. 07. 2007
Příspěvky: 2156
|
| Zaslal: 22. říjen 2010, 14:46:53 Předmět: |
|
|
dobre postaveny prefixovy a postfixovy strom je dosti mala strukturka ...
pokud indexujes podle 4 sloupcu, staci na full-text i jeden strom a dobre zvolena informace v nodech/listech |
|
| Návrat nahoru |
|
|
micky
Založen: 28. 02. 2008
Příspěvky: 348
Bydliště: Plzeň, Praha
|
|
| Návrat nahoru |
|
|
sulthan
Založen: 24. 10. 2007
Příspěvky: 104
|
| Zaslal: 23. říjen 2010, 13:37:43 Předmět: |
|
|
| Zalezi na tom, jak hodne se muzou hodnoty opakovat. Mozna bys pro vyhledavani mohl pouzit jen jeden sloupec a pak jen overit rovnost ostatnich sloupcu? |
|
| Návrat nahoru |
|
|
majkl
Založen: 28. 08. 2007
Příspěvky: 4
|
| Zaslal: 23. říjen 2010, 15:14:48 Předmět: |
|
|
| rezna napsal: |
dobre postaveny prefixovy a postfixovy strom je dosti mala strukturka ...
pokud indexujes podle 4 sloupcu, staci na full-text i jeden strom a dobre zvolena informace v nodech/listech |
No, zapomnel jsem jednu podstatnou informaci.. ty stringy budou unicodove a vyuzivaji opravdu celou tabulku.. zvlast nektere sloupce mohou mit ty retezce temer neprefixovatelne..
Takze zaden fulltext  zrejme proste seradim to pole a pak metodou puleni intervalu, jinak asi nemam sanci... |
|
| Návrat nahoru |
|
|
rezna
Založen: 27. 07. 2007
Příspěvky: 2156
|
| Zaslal: 24. říjen 2010, 08:39:12 Předmět: |
|
|
najdi si co 'TRIE' - pokud planujes vyuzit velke mnozstvi slov bude TRIE znacne mensi nez tabulka ve ktere budes hledat pres stricmp
slozitost u obou je O(log(n))
a mozna taky si najdi co je ten prefixovy strom |
|
| Návrat nahoru |
|
|
|
Hlavní strana
FAQ
Test
Hledat
Seznam uživatelů
Uživatelské skupiny
Registrace
Ke Stažení
Nastavení
Přihlášení
Calendar
