[DSA] Домашно Advanced Data Structures - 3 Задача


2

Условие:

3.Write a program that finds a set of words (e.g. 1000 words) in a large text (e.g. 100 MB text file). Print how many times each word occurs in the text.

Hint: you may find a C# trie in Internet.

Решение - цък

Имплементирам структура от данни Trie. Чете се текстов файл и се вадят всички думи. В Trie е важна позицията на всеки node в масива, което определя какъв е префикса на думата. Във всеки възел знаем броят на думи и префикси. Попълването се оказа доста бавна операция и текста е само 20МБ, иначе не се чака. Добавих и сравняване с речник и поне при мен търсенето на дума е по-бързо при Trie. Може би защото няма ключ и хеширане. 

Текстът е в архив, но е лесно да изтеглите само него от тук. Добавя се в директорията на проекта.

 

Едит: Няколко теста по-късно - резултатите в бързината на Trie са променливи. Но вървят с пренебрежима разлика във времето. Ако някой знае как да преодолее проблема с бавното попълване на думите ще съм му благодарен да сподели.

 

Едит2: Колегата pirin даде предложение, че за конкретният пример би било по-добре да сложа думите, които търся в Trie и после да обхождам всички думи в текста, като ги мачвам със създадените prefix-и и при съвпадение добавям дума. По този начин Trie става много по-малък, а бавната операция е въртенето на думите и инкрементацията на броят на търсените. Върви с около 1.5 сек. по-бързо. Сега разбрах какво е имал предвид Наков, като каза, че търсим всички думи наведнъж. Старата имплементация е запазена в проекта. 




Отговори



2

Доколкото разбирам идеята на трай(trie) е да се ползва когато много пъти ще се търси в един дъъълъг текст една или много думи. Аз го имплементирах в прост вариант, който само казва дали думата я има или не но идеята е същата.

Написах една статийка обясняваща (моето разбиране за) trie. -> article


от gparlakov (884 точки)


1

Един алгоритъм, който решава задачата е Aho–Corasick string matching.

Мисля, че тук е добре обяснено за какво може да се ползва:

http://www.codeproject.com/Articles/12383/Aho-Corasick-string-matching-in-C


от vic.alexiev (2299 точки)


1
А за какво време се справя вашата програма със задачата?
Аз реших да я реша използвайки Bag в който пълня всяка дума от един файл, който е 104 MB, после в друг Bag пъля 1000-та думи. Накрая foreach-вам големия баг като проверявам за всяка дума от големя баг се съдържа в малкия Bag... цялата работа за 11 секунди, но не мога да преценя това бавно ли е или е добре като се има предвид големината на файла?

от todor_pr (1527 точки)


0
а за колко време пълниш двата Bag-a, или 11 секунди е общ всичко


0
Всичко е за 11 сек... в началото на кода пускам Stopwatch-а и в краяна кода го спирам. Добре ли е като време?

от todor_pr (1527 точки)



1

Решение

Страшно интересна задача - търся 1 000 000 думи за 1.06 сек :) Не съм го направил да чете от файл - знам, че това доста ще забави програмата, но мисля, че това не е най-важното в тази задачка. Всички думи са рандом и съм използвал дървовидната структура trie (повече информация тук), чиято имплементация ще се опитам да обясня :

Създавам си клас Node който има стойност char, има int брояч и деца - речник от ключ char i стойност Node.
 
Когато добавям дума тръгвам от корена и проверявам дали децата му(речник) съдържа ключ първата буква на думата. Ако има такъв текущия ноуд става това дете, брояча на това това дете се увеличава с 1 (вече има още една дума която започва с w (примерно)), а търсенето се извършва за втората буква на думата. Ако няма такъв ключ добавям всяка оставаща буква от думата като съответно всяка следваща буква е дете на предната.
 
Когато търся дума тръгвам от корена и докато индекса на буквата която търся не стане равен на дължината на думате която търся (в този момент съм намерил думата и връщам нейната Count стойност - толкова пъти се среща в текста) присвоявам на текущия ноуд детето му с ключ конкретната буква. Ако в даден момент текущия ноуд няма дете което да има за ключ следващата буква от думата return-вам 0 - тази дума явно я няма. Ако думата е част от друга дума (показал съм го на картинката) вадя от тази Count стойност (на картинката r) всички Count стойности на децата (на картинката d и k). Така ако се добави примерно car cars и cars , car ще се среща само 1 път.
 
Накрая от чисто любопитство намирам най-често срещаната дума :)
 
Сигурно не е най-ефективния начин от към памет, но ми се струва достатъчно бързо :)

от dzhenko (3893 точки)


0
Аз използвам Trie ето от тук. Първо построявам Trie-то от един 6MB файл с около 1 милион думи, което отнема 1 секунда (заедно с четенето от файла). От тук нататък идва огромното предимство на Trie-то да реши този тип задачи. Само 4 ms отнема търсенето на 1000 думи сред тези един милион. Имам отделен файл със случайни 1000 думи, и в един ред се построява речника с броя срещания на всяка дума:
 
var dict = searchWords.ToDictionary(=> w, w => trie.WordCount(w));
 
Ето и пълното решение: Source
 

от neutrino (3376 точки)