Szukanie ilości danej frazy w dużych plikach

pytanie zadane 23 kwietnia 2018 w C i C++ przez SzyszeK Nowicjusz (120 p.)

Witam, mój problem polega na stworzeniu programu, które będzie miał za zadanie w piku tekstowym odnaleźć ile razy w nim powtarza się z góry ustalona fraza. Problem w głównej mierze polega na tym, iż sam plik posiada ponad 1300 linii, co sprawia, że po tym jak go napisałem - działał na testowanym małym pliku, ale szukanie frazy w tak wielu liniach nie powiodło się z racji bardzo długiego oczekiwania. Moim pytaniem jest to, czy istnieje jakaś możliwość zoptymalizowania programu, by mógł sprawnie działać. Z góry dziękuję za pomoc i chcę zaznaczyć, iż nie jestem wybitnym znawcą programowania, więc proszę o wyrozumiałość. Poniżej wklejam kod:

#include <iostream>
#include <fstream>

using namespace std;

int frazy=0;

int main()
{
std::fstream plik("przklad.txt");
std::string tekst;
while(!plik.eof())
{
    getline(plik, tekst);
    if(!(std::string::npos == tekst.find("przykladowafraza")))
    frazy++;
}

cout<<"Ilosc powtorzen danej frazy: "<<frazy;

}

Z góry dziękuję za każdą pomoc :D

komentarz 23 kwietnia 2018 przez mokrowski Mędrzec (155,460 p.)

Jak szybkiego działania oczekujesz... realnie?

1300 linii... a ile znaków ma 1 linia?

To jest jakiś plik tekstowy?

1300 linii dla takiego pliku nie wydaje się wartością dość.. "obszerną". Najprawdopodobniej zmieścisz go w pamięci i przeszukasz. Co najwyżej będzie potrzebny Boyer-Moore(-Horspool).

komentarz 23 kwietnia 2018 przez SzyszeK Nowicjusz (120 p.)

Jedna linijka ma około 100 znaków. Nie wiem czy w powyższym kodzie jest błąd, ale nawet po około 8 minutach nie otrzymałem wyniku, więc jestem wręcz przekonany, że można to zrobić szybciej. Nie oczekuję cudów, chcę po prostu, aby nie trwało to w godzinach i nie musiałbym zostawiać komputera na kilkanaście minut, żeby odnaleźć ilość fraz, bo to raczej mija się to z celem.

komentarz 23 kwietnia 2018 przez Sedi Stary wyjadacz (10,200 p.)

Szyszek tak swoją drogą, to jakiego komputera używasz ? Przed chwilą zrobiłem test z odczytem dla 100k różnych słów na wolnym dysku hhd i zajęło to 20 milisekund.

komentarz 23 kwietnia 2018 przez SzyszeK Nowicjusz (120 p.)

Komputer nie jest najgorszą maszyną. Grałem na nim w tytuły takie jak GTA V, Fortnite itp, więc myślę, że raczej tu nie ma problemu.

3 odpowiedzi

odpowiedź 23 kwietnia 2018 przez k222 Nałogowiec (30,150 p.)
edycja 23 kwietnia 2018 przez k222

Jednym ze sposobów optymalizacji która zadzaiłą dla bardzo dużej ilości danych będize drzewo (to się chyba nazywa drzewo słownikowe) - spróbuję przybliżyć ideę chociaż to może być trudne. Masz więc strukturę drzewa, coś w stylu:

struct tree {
int k;
tree *next[32];
}

masz w niej wskaźniki next, jest ich 32 bo są 32 litery w polskim alfabecie. Szukając danego słowa po prostu idziesz po kolei po jego literach czyli np. ala to będzie root, root->next[0] (bo a jest 0 literą), root->next[0]->next[14] (bo l jest jak dobrze policzyłem 14 literą licząc od 0) root->next[0]->next[15]->next[0] (i na końcu znowu a). Oczywiście nie budujesz całego drzewa o wysokości 20 bo to by było strasznie pamięcio i czaso chłonne. Potrzebujesz dwóch operacji - dodawania słowa i szukania słowa. Będą one wyglądały tak: dodawanie słowa - jak dany węzeł z literką istnieje to w niego wchodzisz, jeżeli nie istnieje to go tworzysz. Zauważ że im więcej słów będzie już zrobione, tym mniej nowych węzłów trzeba bedzie tworzyć a jednocześnie będziesz miał tyle węzłów ile potrzebujesz. W tej strukturze jest też zmienna int k - domyślnie ma ona wartość 0, jeżeli na danej literce będzie kończyło się jakieś słowo to po prostu zwiększasz tę wartość o 1, bo np. słowo masa zawiera się w tym drzewie w słowie masakra. Jak więc wspomniałem przez to zawieranie złożoność pamięciowa i czasowa dodawania powinna być w miarę ok, za to złożoność wyszukiwania będzie wręcz cudowna, ponieważ wystarczy iść w dół drzewa wchodząć odpowiednie węzły, jak dojdziemy do końca drzewa (do wskaźnika na NULL) lub wartoś k będzie równa 0 to takiego słowa nie ma w tekście, jak będzie niezerowa to tyle razy to słowo występuje.

Innym sposobem jest tablica z hashowaniem - idea jest taka że masz tablicę n elementów (n musi być dosyć dużę, jest to tablica wskaźników na stringi (w C++ stringi w C albo na strukturę albo na tablicę charów) i teraz każde słowo "przerabiasz na liczbę" - jest to ardzo proste bo wystarczy dodać so siebie kody ASCII liter tego słowa i zrobić modulo n - będzie to klucz. Teraz wystarczy dodać to słowo do tablicy pod indeksem równym kluczowi. Zauważ ze wyszukiwanie będzie polegało na znalezieniu klucza i sporawdzenie czy pod indeksem mu równym coś jest, co jest bardzo szybkie. Oczywiście pozostaje problem że słowa mogą mieć taki sam klucz np. olo i lol - ten problem można rozwiązać jak dana komórka tablicy będzie wskaźnikiem na listę (łańcuch odsyłaczowy) a w niej będą słowa o takich dsamych kluczach (i ew. liczba ich wystąpień w tekście).

Są to dwa sposoby, generalnie troszkę zabawy z zakodzeniem tego będzie, ale oba są szybkie.

komentarz 23 kwietnia 2018 przez Sedi Stary wyjadacz (10,200 p.)

No trochę się napisałeś z tym :D Pomysł z drzewem jest ciekawy, jednocześnie kolega mokrowski wspomniał o algorytmie Boyer-Moore, który jest implementacją praktycznie tego samego co napisałeś, ale iteracyjnie przez co jest szybsze :) Co nie zmienia faktu, że pomysł z hashowaniem jest całkiem ciekawy :)

1	komentarz 23 kwietnia 2018 przez SzyszeK Nowicjusz (120 p.) Postaram się coś takiego zrobić. Dziękuję bardzo za pomoc i rozpisanie rozwiązania, mam nadzieję, iż mimo braku zaawansowanej wiedzy uda mi się coś wskórać.

odpowiedź 23 kwietnia 2018 przez mokrowski Mędrzec (155,460 p.)

IMHO wyszuka Ci wystarczająco szybko ... dla tak małego pliku nie ma co popadać w "optymalizację na siłę":

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cstddef>

constexpr static std::size_t lines_count = 1300;

std::vector<std::string> readFile(const std::string& fileName) {
    std::vector<std::string> lines;
    lines.reserve(lines_count);
    std::string line;
    std::ifstream file(fileName, std::ios::binary);
    // TODO: Check open file error.
    while(file) {
        getline(file, line);
        lines.emplace_back(line);
    }
    return lines;
}

std::size_t countPhrase(const std::vector<std::string>& lines, const std::string& phrase) {
    std::size_t counter = 0;
    for(const auto& line: lines) {
        std::string::size_type pos = 0;
        do {
            pos = line.find(phrase, pos);
            if(pos < std::string::npos) {
                ++counter;
                ++pos;
            }
        } while(pos != std::string::npos);
    }
    return counter;
}

int main() {
    auto lines = readFile("file_name.txt");
    auto count = countPhrase(lines, "example_phrase");
    std::cout << count << '\n';
}

komentarz 23 kwietnia 2018 przez SzyszeK Nowicjusz (120 p.)

warning: identifier 'constexpr' is a keyword in C++11 [-Wc++0x-compat]|

error: 'constexpr' does not name a type|

error: expected ',' or '...' before '.' token|

Albo posiadam zbyt mało wiedzy, żeby to skonfigurować, albo coś tu jest nie tak.

komentarz 23 kwietnia 2018 przez mokrowski Mędrzec (155,460 p.)

Standard C++11 włącz w kompilatorze.. to już 7 lat temu..

komentarz 23 kwietnia 2018 przez mokrowski Mędrzec (155,460 p.)

@SzyszeK, Wersja dla Twojego starego kompilatora... odśwież swoje narzędzia...

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cstddef>

static std::size_t lines_count = 1300;

std::vector<std::string> readFile(const std::string& fileName) {
    std::vector<std::string> lines;
    lines.reserve(lines_count);
    std::string line;
    std::ifstream file(fileName.c_str(), std::ios::binary);
    // TODO: Check open file error.
    while(file) {
        getline(file, line);
        lines.push_back(line);
    }
    return lines;
}

std::size_t countPhrase(const std::vector<std::string>& lines, const std::string& phrase) {
    std::size_t counter = 0;
    std::string line;
    for(std::size_t i = 0; i < lines.size(); ++i) {
        line = lines[i];
        std::string::size_type pos = 0;
        do {
            pos = line.find(phrase, pos);
            if(pos < std::string::npos) {
                ++counter;
                ++pos;
            }
        } while(pos != std::string::npos);
    }
    return counter;
}

int main() {
    std::vector<std::string> lines = readFile("file_name.txt");
    std::size_t count = countPhrase(lines, "example_phrase");
    std::cout << count << '\n';
}

odpowiedź 23 kwietnia 2018 przez .kassad Gaduła (3,420 p.)

Tak jak ktoś już wspomniał, możesz wczytać cały plik do jakiegoś bufora i pracować na tym buforze. Odczytów z dysku będzie kilkadziesiąt. Ładny przykład, jak to zrobić:

std::ifstream file("myfile", std::ios::binary | std::ios::ate);
std::streamsize size = file.tellg();
file.seekg(0, std::ios::beg);

std::vector<char> buffer(size);
if (file.read(buffer.data(), size))
{
    /* worked! */
}

https://stackoverflow.com/questions/18816126/c-read-the-whole-file-in-buffer