Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
MrGluck
Модератор
Эксперт CЭксперт С++
8021 / 4864 / 1425
Регистрация: 29.11.2010
Сообщений: 13,241
#1

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

08.09.2012, 13:36. Просмотров 1193. Ответов 11
Метки нет (Все метки)

Здравствуйте.
По заданию требовалось составить программу для подсчета вхождений разных сочетаний букв с алфавита от 1 буквы до 4 в текстовый файл, размером 1 Мб. Т.е, например, для латиницы это a, b, c, ... z, aa, ... az, aaaa, ..., zzzz. Только алфавит надо было взять не латинский (я взял греческий). Результаты поиска записать в файл .csv через запятую. Программу то я написал, да вот выполняется она минут 80 (проц 2-х ядерный Intel D525 с частотой 1,8 ГГц), но все же, хотелось бы как-нибудь уменьшить эту цифру. Помогите оптимизировать алгоритм. Да, пишу под Linux.
Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.09.2012, 13:36
Я подобрал для вас темы с готовыми решениями и ответами на вопрос оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) (C++):

Оптимизировать алгоритм поиска двух одинаковых фраз, в массиве фраз
Всем привет! Может кто подскажет, как оптимизировать алгоритм поиска 2-х...

Файл: Скопировать текст в другой текстовый файл файл, но чётные строки должны быть с большой буквы...
Создать текстовый файл. Скопировать текст в другой текстовый файл файл, но...

Текстовый файл содержит строки – предложения разной длины. Записать их в выходной файл в порядке возрастания длины строки
ребят всю голову сломал уже завтра уже надо сдавать(( Текстовый файл...

Текстовый файл содержит строки – предложения разной длины. Записать их в выходной файл в порядке возрастания длины строки
Текстовый файл содержит строки – предложения разной длины. Записать их в...

Алгоритм поиска строки в тексте
Здравствуйте!!! Подскажите пожалуйста алгоритм поиска строки P в тексте S за...

Дан исходный текстовый файл. Записать его строки в выходной файл в перевёрнутом виде
грозят отчислением, нужно решить

11
OhMyGodSoLong
~ Эврика! ~
1245 / 994 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
08.09.2012, 14:16 #2
Эм. Делаете четыре массива: одномерный, двухмерный, трёхмерный и четырёхмерный. Размером, соответственно, сколько-букв-в-алфавите по каждому измерению. Заполняете нулями. Там мегабайт памяти или типа того на них надо для греческого.

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

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

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

В принципе, можно даже обойтись одним буфером на четыре символа. И одним четырёхмерным массивом (выделить, к примеру, двадцать пятую букву под меньшую размерность).
1
Герц
524 / 341 / 12
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
08.09.2012, 14:24 #3
Смотри в сторону суффиксных деревьев. Есть хорошая книжка Гасфилда по алгоритмам на строках.
1
OhMyGodSoLong
~ Эврика! ~
1245 / 994 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
08.09.2012, 14:26 #4
fix:
если это не буква, ничего не делаем сбрасываем буферы
0
outoftime
║XLR8║
756 / 656 / 211
Регистрация: 25.07.2009
Сообщений: 3,289
Записей в блоге: 5
08.09.2012, 15:51 #5
Дай свой файл для теста, напишу покажу что вышло.

П.С. алгоритмы 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
1
MrGluck
Модератор
Эксперт CЭксперт С++
8021 / 4864 / 1425
Регистрация: 29.11.2010
Сообщений: 13,241
08.09.2012, 16:32  [ТС] #6
Спасибо, много полезной информации.
Файл с текстом. https://dl.dropbox.com/u/24221707/text.txt
А вхождения нужно искать для каждого сочетания от a до zzzz, а ответ выглядит например так:
a, 2011
b, 1789
...
zzzz 0
0
outoftime
║XLR8║
756 / 656 / 211
Регистрация: 25.07.2009
Сообщений: 3,289
Записей в блоге: 5
08.09.2012, 21:19 #7
MrGluck, надо и прописные и строчные символы?

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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
1
2
3
4
5
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.
1
outoftime
║XLR8║
756 / 656 / 211
Регистрация: 25.07.2009
Сообщений: 3,289
Записей в блоге: 5
08.09.2012, 22:07 #8
Весело было поиграться с boost::program_options. Поищи в нете Ахо-Корасика готового и распаралеливание сделай.
1
Вложения
Тип файла: zip StringTest.zip (8.8 Кб, 10 просмотров)
MrGluck
Модератор
Эксперт CЭксперт С++
8021 / 4864 / 1425
Регистрация: 29.11.2010
Сообщений: 13,241
09.09.2012, 02:31  [ТС] #9
outoftime, нужно только строчные с алфавита. В греческом 24 буквы, но одну особенную обозначают 2 символами (выходит 25, не задавать же диапазон из 2 отрезков).
Буду вкуривать Ахо-Карасика . Чувствую, много кофе уйдет. Распараллеливание пока точно не трону (лвл не тот).
0
outoftime
║XLR8║
756 / 656 / 211
Регистрация: 25.07.2009
Сообщений: 3,289
Записей в блоге: 5
09.09.2012, 13:10 #10
MrGluck, а я наоборот, написал КМП и пробую распаралелить, еще добавил индикация прогресса. Кстати, если ты не заметил файл со строками что надо искать занимают 2.3 метра а сам текст 1 метр.

Добавлено через 10 часов 19 минут
Задача в лоб решается элементарно, полный перебор рулит.
1
Вложения
Тип файла: zip StringTest_fullcheck.zip (8.7 Кб, 10 просмотров)
outoftime
║XLR8║
756 / 656 / 211
Регистрация: 25.07.2009
Сообщений: 3,289
Записей в блоге: 5
09.09.2012, 16:20 #11
http://paste.ubuntu.com/1193704/
0
MrGluck
Модератор
Эксперт CЭксперт С++
8021 / 4864 / 1425
Регистрация: 29.11.2010
Сообщений: 13,241
10.09.2012, 13:20  [ТС] #12
Почитав Ахо-Корасика и про суффиксальные деревья, меня натолкнула на мысль одна идея. Вот, в корни переделал алгоритм. Теперь выполняет за 15 секунд (для нетбука неплохо).
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#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; } );
}
0
10.09.2012, 13:20
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.09.2012, 13:20
Привет! Вот еще темы с решениями:

Что не так? Дан текстовый файл F. Переписать в другой файл G все строки, содержащие цифры.
#include &lt;iostream&gt; #include &lt;math.h&gt; using std::cin; using std::cout;...

Текстовый файл состоит из нескольких строк. Записать во второй файл последние символы из каждой строки первого файла
Текстовый файл состоит из нескольких строк. Записать во второй файл последние...

Найти все вхождения строки P в текст T, используя наивный алгоритм поиска
Только начал изучать язык С++, не могу никак реализовать: даны строки P и T....

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru