оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб)

MrGluck · Регистрация: 29.11.2010

Author24 — интернет-сервис помощи студентам

Здравствуйте.
По заданию требовалось составить программу для подсчета вхождений разных сочетаний букв с алфавита от 1 буквы до 4 в текстовый файл, размером 1 Мб. Т.е, например, для латиницы это a, b, c, ... z, aa, ... az, aaaa, ..., zzzz. Только алфавит надо было взять не латинский (я взял греческий). Результаты поиска записать в файл .csv через запятую. Программу то я написал, да вот выполняется она минут 80 (проц 2-х ядерный Intel D525 с частотой 1,8 ГГц), но все же, хотелось бы как-нибудь уменьшить эту цифру. Помогите оптимизировать алгоритм. Да, пишу под Linux.
Вот код:

C++

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstddef>
#define N 4
 
class Alphabet
{
    int tick[N];
    std::vector<char> all;
    bool stop;
  public:
    Alphabet();
    void entry(std::string, std::ostream &);
    Alphabet& operator ++();
    bool isStop() {return stop; }
};  
 
unsigned long countEntry(const std::string &, const std::string &);
 
int main()
{
    std::ifstream ifstext("text.txt");
    std::ofstream o("result.csv");
    if(!ifstext)
    {
        std::cout<< "No file\n";
        return 1;
    }
    std::string text;
    ifstext >> std::noskipws; // clears the scipws flag for the str stream
    std::copy(std::istream_iterator<char>(ifstext), std::istream_iterator<char>(), std::back_inserter(text));
    Alphabet a;
    std::cout<< "Please wait"<< std::endl;
    while (!a.isStop())
        (++a).entry(text, o);
    return 0;
}
 
unsigned long countEntry(const std::string &s, const std::string &delim)
{
    unsigned long counter = 0, found = s.find(delim); // found - number, where we start finding
    if (found != std::string::npos) counter++; // if in first position
    while(true)
    {
        found = s.find(delim, found + 1);
        if (found != std::string::npos) counter++;
        else break;
    }
    return counter;
}   
 
Alphabet::Alphabet()
{
    stop = false;
    for (int i=0; i < N; i++) 
        tick[i] = -1;
    for (int i=0x03E1; i < 0x03FA; i++)
        all.push_back( char(i) );
}
 
void Alphabet::entry(std::string text, std::ostream &o)
{
    if (stop) return;
    std::string str;
    for (int i=0; i < N; i++)
        if (tick[i] != -1)
           str.push_back( all[ tick[i] ] );
    o<< str<< ", "<< countEntry(text, str)<< std::endl;
}
 
Alphabet& Alphabet::operator ++()
{
    tick[N-1]++;
    for (int i = N-1; i > 0; i--) 
    if (tick[i] == all.size())
    {
        /*if (i == 1) // show new procent
        {
            std::cout<< "|";
            std::cout.flush(); // output stream buffer
        }*/
        tick[i - 1]++;
        tick[i] -= all.size();
    }
    if (tick[0] == all.size())
        stop = true;
    return *this;
}

@OhMyGodSoLong · 08.09.2012, 14:16

Эм. Делаете четыре массива: одномерный, двухмерный, трёхмерный и четырёхмерный. Размером, соответственно, сколько-букв-в-алфавите по каждому измерению. Заполняете нулями. Там мегабайт памяти или типа того на них надо для греческого.

Делаете четыре циклических буфера (на основе std::deque): на один, два, три и четыре символа соответственно.

Читаете файл посимвольно, если это не буква, ничего не делаем, если буква — заносим её во все буферы с конца. Если буфер полный, то предварительно выкидываем первый символ, чтобы в буфере всегда было один–четыре символа соответственно.

После каждого чтения буквы смотрим на полные буферы и делаем +1 в каждый из массивов по координатам, соответствующих символам, хранящимся в буфере.

В принципе, можно даже обойтись одним буфером на четыре символа. И одним четырёхмерным массивом (выделить, к примеру, двадцать пятую букву под меньшую размерность).

@Герц · 08.09.2012, 14:24

Смотри в сторону суффиксных деревьев. Есть хорошая книжка Гасфилда по алгоритмам на строках.

@OhMyGodSoLong · 08.09.2012, 14:26

fix:
если это не буква, ~~ничего не делаем~~ сбрасываем буферы

@outoftime · 08.09.2012, 15:51

Дай свой файл для теста, напишу покажу что вышло.

П.С. алгоритмы http://e-maxx.ru/algo/prefix_function http://e-maxx.ru/algo/rabin_karp

Добавлено через 1 час 22 минуты
MrGluck, еще такой момент, я так и не понял ты ищешь вхождение 1 подстроки или массива

C++

1	{"a", "aaa", "aaaa", "aaaa", ..., "z", "zz", "zzz", "zzzz"}

?
Во втором случае тебе надо этот: http://e-maxx.ru/algo/aho_corasick

MrGluck · 08.09.2012, 16:32 **[ТС]**

Спасибо, много полезной информации.
Файл с текстом. https://dl.dropbox.com/u/24221707/text.txt
А вхождения нужно искать для каждого сочетания от a до zzzz, а ответ выглядит например так:
a, 2011
b, 1789
...
zzzz 0

@outoftime · 08.09.2012, 21:19

MrGluck, надо и прописные и строчные символы?

Добавлено через 27 минут
Никогда не любил комбинаторику...

C++

#include <vector>
 
using namespace std;
 
int main () {
        register int i[4], res = 0, n = 'z'-'a';
        for (i[0] = 0; i[0] < n; ++i[0]) {
                for (i[1] = 0; i[1] < n; ++i[1]) {
                        for (i[2] = 0; i[2] < n; ++i[2]) {
                                for (i[3] = 0; i[3] < n; ++i[3]) {
                                        ++res;
                                }
                        }
                }
        }
        cout << res << endl;
}

output:

Bash

ruslan@ruslan-K53TA:~/Documents/StringTest$ vim test.cpp 
ruslan@ruslan-K53TA:~/Documents/StringTest$ g++ -x c++ test.cpp -c
ruslan@ruslan-K53TA:~/Documents/StringTest$ g++ test.o -o test
ruslan@ruslan-K53TA:~/Documents/StringTest$ ./test 
390625

У нас получается 390625 подстрок надо найти в файле с ~1M символов.
1. Здесь без вопросос только Ахо-Корасика надо
2. Можно еще распаралелить. Оптимальным количеством потоков считается N+2, где N - количество ядер процессора. Я бы для этого дела использовал boost::thread так как native pthread на линухе мне не нрав.

Раньше я мог дать оценку времени выполнения исходя с асимптотики, но сейчас мощности очень выросли, затрудняюсь ответить.

Добавлено через 3 минуты
UPD: Спец символы надо? Я видел в файле цифры, знаки препинания скобки...

Добавлено через 4 часа 12 минут
Мда, а гречесский текст найти сложно? Это не гречесский алфавит, и такст также. В гречесском алвафите всего 24 символа, а утебя около 28.

@outoftime · 08.09.2012, 22:07

Весело было поиграться с boost::program_options. Поищи в нете Ахо-Корасика готового и распаралеливание сделай.

MrGluck · 09.09.2012, 02:31 **[ТС]**

outoftime, нужно только строчные с алфавита. В греческом 24 буквы, но одну особенную обозначают 2 символами (выходит 25, не задавать же диапазон из 2 отрезков).
Буду вкуривать Ахо-Карасика

. Чувствую, много кофе уйдет. Распараллеливание пока точно не трону (лвл не тот).

@outoftime · 09.09.2012, 13:10

MrGluck, а я наоборот, написал КМП и пробую распаралелить, еще добавил индикация прогресса. Кстати, если ты не заметил файл со строками что надо искать занимают 2.3 метра а сам текст 1 метр.

Добавлено через 10 часов 19 минут
Задача в лоб решается элементарно, полный перебор рулит.

@outoftime · 09.09.2012, 16:20

http://paste.ubuntu.com/1193704/

MrGluck · 10.09.2012, 13:20 **[ТС]**

Почитав Ахо-Корасика и про суффиксальные деревья, меня натолкнула на мысль одна идея. Вот, в корни переделал алгоритм. Теперь выполняет за 15 секунд (для нетбука неплохо).

C++

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
#include <iterator>
#include <cstddef>
#define N 4
 
struct comp // comparison in map
{
    bool operator()(const std::string &str1, const std::string &str2)
    {
        return str1.length() == str2.length() ? str1 < str2 : str1.length() < str2.length();
    }
};
 
typedef std::map <std::string, unsigned int, comp> map_string_uint;
 
class Combinations
{
    map_string_uint allcomb;
    std::vector<char> alphabet;
  public:
    Combinations();
    void entry(const std::string &);
    void print(std::ostream &);
};
 
int main()
{
    std::ifstream ifstext("text.txt");
    std::ofstream o("result.csv");
    if (!ifstext)
    {
        std::cerr<< "No file\n";
        return 1;
    }
    std::string text;
    ifstext >> std::noskipws; // clears the scipws flag for the str stream
    std::copy(std::istream_iterator<char>(ifstext), std::istream_iterator<char>(), 
          std::back_inserter(text) );
    std::cout<< "Text downloaded in buffer"<< std::endl;
    Combinations c;
    std::cout<< "Combinations compiled"<< std::endl;
    c.entry(text);
    std::cout<< "Writing results in file"<< std::endl;
    c.print(o);
    std::cout<< "Completed"<< std::endl;
    return 0;
}
 
Combinations::Combinations()
{
    for (int i=0x03E1; i < 0x03FA; i++) // forming alphabet
        alphabet.push_back( char(i) );
    int tick[N];
    std::fill(tick, tick + N-1, -1);
    tick[N-1] = 0;
    std::string str;
    while (tick[0] != alphabet.size())
    {
        // forming new combination
        str.clear();
        for (int i=0; i < N; i++)
            if (tick[i] != -1)
                str.push_back( alphabet[ tick[i] ] );
        allcomb.insert( std::make_pair(str, 0) );
        tick[N-1]++; // incriminating combination
        for (int i=N-1; i > 0; i--) // if need increase capacity (разрядность)
            if (tick[i] == alphabet.size())
            {
                tick[i - 1]++;
                tick[i] -= alphabet.size();
            }
    }
}
 
void Combinations::entry(const std::string &text)
{
    std::string buf;
    for (int i=0; i < text.length(); i++)
    {
        for (int j=0; j < N && i + j < text.length(); j++)
        {
            if (std::binary_search (alphabet.begin(), alphabet.end(), text[i + j]) )
                buf.push_back( text[i + j] );
            else break;
        }
        // incriminating counter
        if (!buf.empty() )
        { 
            ++allcomb[buf];
            buf.clear();
        }
    }
}                
 
void Combinations::print(std::ostream &o)
{
    std::for_each(allcomb.begin(), allcomb.end(), [&o](const std::pair <std::string, int> &p)
        { o<< p.first<< ", "<< p.second<< std::endl; } );
}

Добавлено через 29 минут
С компаратором неверно считает... Почему?

Добавлено через 17 часов 40 минут
Исправил ошибку, вот конечный исходник. Результаты работы совпадают с результатами брутаса (1 вариант).

C++

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
#include <iterator>
#include <cstddef>
#define N 4
 
struct comp // comparison in map
{
    bool operator()(const std::string &str1, const std::string &str2) const
    {
        return (str1.length() == str2.length() ? str1 < str2 : str1.length() < str2.length() );
    }
};
 
typedef std::map <std::string, unsigned int, comp> map_string_uint;
 
class Combinations
{
    map_string_uint allcomb;
    std::vector<char> alphabet;
  public:
    Combinations();
    void entry(const std::string &);
    void print(std::ostream &);
};
 
int main()
{
    std::ifstream ifstext("text.txt");
    std::ofstream o("result.csv");
    if (!ifstext)
    {
        std::cerr<< "No file\n";
        return 1;
    }
    std::string text;
    ifstext >> std::noskipws; // clears the scipws flag for the str stream
    std::copy(std::istream_iterator<char>(ifstext), std::istream_iterator<char>(), 
          std::back_inserter(text) );
    std::cout<< "Text downloaded in buffer"<< std::endl;
    Combinations c;
    std::cout<< "Combinations compiled"<< std::endl;
    c.entry(text);
    std::cout<< "Writing results in file"<< std::endl;
    c.print(o);
    std::cout<< "Completed"<< std::endl;
    return 0;
}
 
Combinations::Combinations()
{
    for (int i=0x03E1; i < 0x03FA; i++) // forming alphabet
        alphabet.push_back( char(i) );
    int tick[N];
    std::fill(tick, tick + N-1, -1);
    tick[N-1] = 0;
    std::string str;
    while (tick[0] != alphabet.size())
    {
        // forming new combination
        str.clear();
        for (int i=0; i < N; i++)
            if (tick[i] != -1)
                str.push_back( alphabet[ tick[i] ] );
        allcomb.insert( std::make_pair(str, 0) );
        tick[N-1]++; // incriminating combination
        for (int i=N-1; i > 0; i--) // if need increase capacity (разрядность)
            if (tick[i] == alphabet.size())
            {
                tick[i - 1]++;
                tick[i] -= alphabet.size();
            }
    }
}
 
void Combinations::entry(const std::string &text)
{
    std::string buf;
    for (int i=0; i < text.length(); i++)
    {
        for (int j=0; j < N && i + j < text.length(); j++)
        {
            if (std::binary_search (alphabet.begin(), alphabet.end(), text[i + j]) )
            {
                buf.push_back( text[i + j] );
                ++allcomb[buf]; // incriminating counter
            }
            else break;
        }
        buf.clear();
    }
}                
 
void Combinations::print(std::ostream &o)
{
    std::for_each(allcomb.begin(), allcomb.end(), [&o](const std::pair <std::string, int> &p)
        { o<< p.first<< ", "<< p.second<< std::endl; } );
}

@OhMyGodSoLong ~ Эврика! ~ 1256 / 1005 / 74 Регистрация: 24.07.2012 Сообщений: 2,002
	08.09.2012, 14:16	2
	Эм. Делаете четыре массива: одномерный, двухмерный, трёхмерный и четырёхмерный. Размером, соответственно, сколько-букв-в-алфавите по каждому измерению. Заполняете нулями. Там мегабайт памяти или типа того на них надо для греческого. Делаете четыре циклических буфера (на основе std::deque): на один, два, три и четыре символа соответственно. Читаете файл посимвольно, если это не буква, ничего не делаем, если буква — заносим её во все буферы с конца. Если буфер полный, то предварительно выкидываем первый символ, чтобы в буфере всегда было один–четыре символа соответственно. После каждого чтения буквы смотрим на полные буферы и делаем +1 в каждый из массивов по координатам, соответствующих символам, хранящимся в буфере. В принципе, можно даже обойтись одним буфером на четыре символа. И одним четырёхмерным массивом (выделить, к примеру, двадцать пятую букву под меньшую размерность). 1

@Герц 545 / 344 / 12 Регистрация: 05.11.2010 Сообщений: 1,076 Записей в блоге: 1
	08.09.2012, 14:24	3
	Смотри в сторону суффиксных деревьев. Есть хорошая книжка Гасфилда по алгоритмам на строках. 1

@OhMyGodSoLong ~ Эврика! ~ 1256 / 1005 / 74 Регистрация: 24.07.2012 Сообщений: 2,002
	08.09.2012, 14:26	4
	fix: если это не буква, ~~ничего не делаем~~ сбрасываем буферы 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	08.09.2012, 16:32 [ТС]	6
	Спасибо, много полезной информации. Файл с текстом. https://dl.dropbox.com/u/24221707/text.txt А вхождения нужно искать для каждого сочетания от a до zzzz, а ответ выглядит например так: a, 2011 b, 1789 ... zzzz 0 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	09.09.2012, 02:31 [ТС]	9
	outoftime, нужно только строчные с алфавита. В греческом 24 буквы, но одну особенную обозначают 2 символами (выходит 25, не задавать же диапазон из 2 отрезков). Буду вкуривать Ахо-Карасика . Чувствую, много кофе уйдет. Распараллеливание пока точно не трону (лвл не тот). 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5
	09.09.2012, 16:20	11
	http://paste.ubuntu.com/1193704/ 0

	10.09.2012, 13:20