You are here: PSPad forum > České diskuzní fórum > Re: vyhledávací mechanismus PSPadu

Re: vyhledávací mechanismus PSPadu

#1 vyhledávací mechanismus PSPadu

Posted by: 4ever | Date: 09/13/2017 21:08 | IP: IP Logged

Nedávno jsem hledal nějakou databázi českých slovíček na internetu a náhodou jsem se dostal na link vedoucí na soubor cab s obsahem Czech.3-2-5.dic. Zkusil jsem to otevřít a vyhledat pár slovíček a docela mě překvapuje že PSPad dokáže v tak velkém množství slovíček tak rychle hledat. Zajímá mě, máte na to nějaký fígl (chytrý algoritmus)? Jako příklad uvedu slovo Žďársko, které mi to najde asi za 1s. Přitom je ten záznam až na řádku 925678. Myslím že na to musíte mít nějaký algoritmus, nebo hledat v 10MB řetězci by asi jinak trvalo déle, ne?

Options: Reply | Quote | Up ^


#2 Re: vyhledávací mechanismus PSPadu

Posted by: pspad | Date: 09/14/2017 05:29 | IP: IP Logged

Hledání je obyčejnou hrubou silou - tam se nedá předpokládat žádné řazení souboru, pracuje se s obecným textem.
Co se týká algoritmů, spíš je zajímavější kontrola pravopisu, protože ta kontroluje v reálném čase aktuální stránku právě za využití slovníku. Tam není možné čekat sekundy nebo desetiny sekund na každé slovo.
Při načtení slovníku se slovník seřadí a vytvoří se index. Při vyhledávání slova se pak prohledává pouze část slovníku - místo milionů slov se hledá ve stovkách.

Options: Reply | Quote | Up ^


#3 Re: vyhledávací mechanismus PSPadu

Posted by: 4ever | Date: 09/14/2017 11:09 | IP: IP Logged

Chtěl bych napsat program, který bude určovat gramatiku, slovní druhy, pády, skloňování, apod. S indexováním tam mi to je jasné. Mám představu jak bych to udělal aby to hledalo velmi rychle. Jen to hledání přímo v textu mi vrtalo hlavou. Ono by se možná i něco na urychlení vymyslet dalo, ale bylo by to složité.

Options: Reply | Quote | Up ^


#4 Re: vyhledávací mechanismus PSPadu

Posted by: 4ever | Date: 09/14/2017 12:31 | IP: IP Logged

Jen pro zajímavost co mě napadlo, že by se dalo udělat. Bylo by to náročnější na paměť. Soubor by měl být víceméně jen pro čtení. Za předpokladu, že uživatel chce hledat běžný text, případně čísla... Velikost v paměti by se zdvounásobila, pokud by chtěl hledat i s ohledem na velikost znaků

Základní abeceda má myslím 26 znaků + 10 čísel + oddělovače jako čárka, středník, pomlčka, podtržítko. tj 40 znaků (=> 40 možných separátorů). Rozparsovat soubor pomocí prvního separátoru "a" nebo "A" (bez ohledu na velikost písmene). Tím získáš první pole a_arr, které bude zabírat +/- 10MB. Další znak bude "b". Rozparsuješ originální soubor získáš b_arr atd. Rozparsuješ všechny a bude ti to v paměti zabírat cca 400MB (660MB sada i s uppercase oddělovačem).

Samotné hledání by probíhalo tak, že když uživatel zadá hledaný text např. "ten, který", použiješ pole kde je čárka jako oddělovač. Projdeš všechny pole a hledáš slovo "který" pouze na začátku každého elementu pole. Když najdeš, zkontroluješ jestli předchozí element končí na slovo "ten". Pokud ano, pak si našel slovo. Takto by se dalo mnohonásobně urychlit hledání. Pro úsporu místa v paměti by se nepoužívaná pole dala dočasně uložit na disk.

Má to ale nevýhodu, že se to musí nejdříve celé 40 nebo 66x rozparsovat. Multiprocessing by to mohl trochu urychlit.

Edited 2 time(s). Last edit at 09/14/2017 12:37 by 4ever.

Options: Reply | Quote | Up ^


#5 Re: vyhledávací mechanismus PSPadu

Posted by: pspad | Date: 09/14/2017 12:41 | IP: IP Logged

Jen podotknu, že není možné se spoléhat na základní abecedu, protože "zahraniční" uživatelé běžně píší kód v latince a řetězce třeba v azbuce nebo čínštině. Takže je třeba počítat s plnou UNICODE sadou, čímž se z toho stává obluda, které by nestačila paměť a při ukládání na disk by zabrala půl disku.
A vygenerování toho souboru by trvalo mnohem déle než hledání "hrubou silou"

Options: Reply | Quote | Up ^


#6 Re: vyhledávací mechanismus PSPadu

Posted by: 4ever | Date: 09/15/2017 20:18 | IP: IP Logged

S tím souhlasím. Ono by to spíš chtělo udělat to dotyčnému na míru, aby si mohl zadat znak(), který by byl použitý jako oddělovač. Mohl by si vybrat ze znaků abecedy nebo sady, kterou používá a tím by se to vyřešilo. Bez multiprocessingu by to trvalo dlouho. Moderní technologie se ale ubírají směrem, že multiprocesing bude hrát klíčovou roli v budoucnu. Tohle by byl dobrý příklad jak ho využít. Myslím teda že za deset let už nebude 16-32 threadový procesor žádnou novinkou.

Edited 2 time(s). Last edit at 09/15/2017 20:22 by 4ever.

Options: Reply | Quote | Up ^






Editor PSPad - freeware editor, © 2001 - 2017 Jan Fiala
Hosted by Webhosting TOJEONO.CZ, design by WebDesign PAY & SOFT, code Petr Dvořák