Новичок
Профиль
Группа: Участник
Сообщений: 2
Регистрация: 1.9.2007
Репутация: нет
Всего: нет
|
Всем доброго бодрого времени суток. Имеется класс по обработке текста по огромному словарю за очень быстрое время. Используется так называемый алгоритм Ахо-Карасика. Суть не в этом. Вот он сам класс: Код C++ | Код |
class AhoCorasick
{
public:
typedef void (*Callback) (const char* substr, int begin, int end);
~AhoCorasick()
{
queue<BorNode*> q;
for(map<char, BorNode*>::const_iterator iter = root.links.begin();
iter != root.links.end(); ++iter)
q.push(iter->second);
while(!q.empty())
{
BorNode* current_node = q.front();
q.pop();
for(map<char, BorNode*>::const_iterator iter = current_node->links.begin();
iter != current_node->links.end(); ++iter)
q.push(iter->second);
delete current_node;
}
}
// Метод добавляет строку в бор
void AddString(const char* str, AnsiString strIndex)
{
/*bool status_word = 0;
for (int y=0; y<words.size();y++) {
if (str == words[y])
status_word = 1;
}
if (status_word == 0)
{ */
BorNode* node = &root;
for(const char* s = str; *s; ++s)
{
map<char, BorNode*>::iterator iter = node->links.find(*s);
if(iter != node->links.end())
node = iter->second;
else
{
BorNode* new_node = new BorNode;
node->links[*s] = new_node;
node = new_node;
}
}
node->out = words.size();
words.push_back(str);
Voc_Indexes.push_back(strIndex);
//}
}
// Метод вычисляет функции неудачи
void Init()
{
root.fail = &root;
queue<BorNode*> q;
q.push(&root);
while(!q.empty())
{
BorNode* current_node = q.front();
q.pop();
for(map<char, BorNode*>::const_iterator iter = current_node->links.begin();
iter != current_node->links.end(); ++iter)
{
BorNode* child = iter->second;
char symb = iter->first;
q.push(child);
BorNode* parent_fail = current_node->fail;
while(true)
{
map<char, BorNode*>::const_iterator it = parent_fail->links.find(symb);
if(it != parent_fail->links.end())
{
child->fail = it->second != child ? it->second : &root;
if(child->out < 0)
child->out = child->fail->out;
break;
}
if(parent_fail == &root)
{
child->fail = &root;
break;
}
else
parent_fail = parent_fail->fail;
}
}
}
}
AnsiString Search(const char* str, Callback callback)
{
BorNode* current_node = &root;
AnsiString return_str = "";
for(int pos = 1; *str; ++str, ++pos)
{
map<char, BorNode*>::const_iterator iter = current_node->links.find(*str);
while(iter == current_node->links.end())
{
current_node = current_node->fail;
iter = current_node->links.find(*str);
if(current_node == current_node->fail)
break;
}
if(iter != current_node->links.end())
{
current_node = iter->second;
//==== если что-то нашли =====
if(current_node->out >= 0) {
if (return_str.Pos(Voc_Indexes[current_node->out]) == 0)
{
return_str = return_str + Voc_Indexes[current_node->out];
}
//========== нашли и ищем дальше ===============
callback(words[current_node->out].c_str(), pos - words[current_node->out].length(), pos - 1);
}
}
}
return return_str;
}
private:
struct BorNode
{
BorNode() : fail(NULL), out(-1) {}
map<char, BorNode*> links;
BorNode* fail;
int out;
};
BorNode root;
vector<string> words;
vector<AnsiString> Voc_Indexes;
};
|
Вся загвоздка в нижеприведенном коде: Код C++ | Код |
AhoCorasick VOCS_AK[100];
void PreloadAhoCorasik()
{
int j=1;
//-------------------------------------------
AnsiString VocIndexes;
//-------------------------------------------
Form1->ProgressBar1->MaxValue = MyPotoks.size();
Form1->ProgressBar1->MinValue = 0;
Form1->Panel6->Visible = true;
//VOCS_AK.clear();
for (int i=0; i<MyPotoks.size();i++)
{
AhoCorasick VOC_AK;
Form1->ProgressBar1->Progress = i;
Form1->lProcent->Caption = "Инициализация по потоку: " + MyPotoks[i].potok_array;
Form1->lProcent->Left = (Form1->Panel6->Width)/2 - (Form1->lProcent->Width)/2;
Application->ProcessMessages();
for (int my_word = 0; my_word < POTOKS_WORDS_OTOBR[i].voc_words.size(); my_word++)
{
VOCS_AK[i].AddString(POTOKS_WORDS_OTOBR[i].voc_words[my_word].c_str(), POTOKS_WORDS_OTOBR[i].world_voc_str[my_word]);
}
//========== Прогресс бар создания общих по потокам словарей ====
VOCS_AK[i].Init();
Form1->ProgressBar1->Progress = i;
Application->ProcessMessages();
}
Form1->Panel6->Visible = false;
}
|
В данном случае я сразу устанавливаю размер VOCS_AK равным ста элементам. В таком случае при вызове функции PreloadAhoCorasik() все работает, программа съедает метров 200 оперативки, то нормально, так как грузится 100 словарей по 40000 слов Ансистринга. Есть неоходимость вызывать эту функцию еще раз, в таком случае происходят некоторые утечки памяти, раза после 50-го программа сжирает уж слишком много оперативки. Это еще полбеды. может КТО ПОДСКАЖЕТ как найти утечку в таком случае. Второй вариант функции: Код C++ | Код |
vector <AhoCorasick> VOCS_AK;
void PreloadAhoCorasik()
{
int j=1;
//-------------------------------------------
AnsiString VocIndexes;
//-------------------------------------------
Form1->ProgressBar1->MaxValue = MyPotoks.size();
Form1->ProgressBar1->MinValue = 0;
Form1->Panel6->Visible = true;
VOCS_AK.clear();
for (int i=0; i<MyPotoks.size();i++)
{
AhoCorasick VOC_AK;
VOCS_AK.push_back(VOC_AK);
// или можно так, без разницы VOCS_AK.push_back();
Form1->ProgressBar1->Progress = i;
Form1->lProcent->Caption = "Инициализация по потоку: " + MyPotoks[i].potok_array;
Form1->lProcent->Left = (Form1->Panel6->Width)/2 - (Form1->lProcent->Width)/2;
Application->ProcessMessages();
for (int my_word = 0; my_word < POTOKS_WORDS_OTOBR[i].voc_words.size(); my_word++)
{
VOCS_AK[i].AddString(POTOKS_WORDS_OTOBR[i].voc_words[my_word].c_str(), POTOKS_WORDS_OTOBR[i].world_voc_str[my_word]);
}
//========== Прогресс бар создания общих по потокам словарей ====
VOCS_AK[i].Init();
Form1->ProgressBar1->Progress = i;
Application->ProcessMessages();
}
Form1->Panel6->Visible = false;
}
|
сразу скажу не надо винить к примеру вектор POTOKS_WORDS_OTOBR и т.п., там все ок. Это глобальные переменные.... В общем проблема в этом лучае такова, что не удается вызвать функцию PreloadAhoCorasik() даже один раз, так в цикле как при i=2, именно двум, Код C++ | Код |
VOCS_AK.push_back(VOC_AK);
// или можно так, без разницы VOCS_AK.push_back(); |
выдает ошибку памяти, толи не выделена память , толи еще что. В общем есть огромная необходимость разобраться в этом куске кода и реализовать хотя бы один из вариантов. Возможно надо поправить класс. И огромная просьба не говорить слишком умными словами. Заранее всем спасибо. )) Ниже приведен целиком первый вариант модуля cpp Добавлено через 1 минуту и 37 секундКод C++ | Код |
//---------------------------------------------------------------------------
#pragma hdrstop
#include "SrchWdsInFlsUnit.h"
#include "UnitGlobalVariables.h"
#include "UnitVocs.h"
#include "main.h"
#include <mem.h>
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <queue>
//---------------------------------------------------------------------------
#pragma package(smart_init)
//===========================================================================
//---------------------------------------------------------------------------
#define ASIZE 1024
typedef unsigned char byte;
using namespace std;
class AhoCorasick
{
public:
typedef void (*Callback) (const char* substr, int begin, int end);
~AhoCorasick()
{
queue<BorNode*> q;
for(map<char, BorNode*>::const_iterator iter = root.links.begin();
iter != root.links.end(); ++iter)
q.push(iter->second);
while(!q.empty())
{
BorNode* current_node = q.front();
q.pop();
for(map<char, BorNode*>::const_iterator iter = current_node->links.begin();
iter != current_node->links.end(); ++iter)
q.push(iter->second);
delete current_node;
}
}
// Метод добавляет строку в бор
void AddString(const char* str, AnsiString strIndex)
{
/*bool status_word = 0;
for (int y=0; y<words.size();y++) {
if (str == words[y])
status_word = 1;
}
if (status_word == 0)
{ */
BorNode* node = &root;
for(const char* s = str; *s; ++s)
{
map<char, BorNode*>::iterator iter = node->links.find(*s);
if(iter != node->links.end())
node = iter->second;
else
{
BorNode* new_node = new BorNode;
node->links[*s] = new_node;
node = new_node;
}
}
node->out = words.size();
words.push_back(str);
Voc_Indexes.push_back(strIndex);
//}
}
// Метод вычисляет функции неудачи
void Init()
{
root.fail = &root;
queue<BorNode*> q;
q.push(&root);
while(!q.empty())
{
BorNode* current_node = q.front();
q.pop();
for(map<char, BorNode*>::const_iterator iter = current_node->links.begin();
iter != current_node->links.end(); ++iter)
{
BorNode* child = iter->second;
char symb = iter->first;
q.push(child);
BorNode* parent_fail = current_node->fail;
while(true)
{
map<char, BorNode*>::const_iterator it = parent_fail->links.find(symb);
if(it != parent_fail->links.end())
{
child->fail = it->second != child ? it->second : &root;
if(child->out < 0)
child->out = child->fail->out;
break;
}
if(parent_fail == &root)
{
child->fail = &root;
break;
}
else
parent_fail = parent_fail->fail;
}
}
}
}
AnsiString Search(const char* str, Callback callback)
{
BorNode* current_node = &root;
AnsiString return_str = "";
for(int pos = 1; *str; ++str, ++pos)
{
map<char, BorNode*>::const_iterator iter = current_node->links.find(*str);
while(iter == current_node->links.end())
{
current_node = current_node->fail;
iter = current_node->links.find(*str);
if(current_node == current_node->fail)
break;
}
if(iter != current_node->links.end())
{
current_node = iter->second;
//==== если что-то нашли =====
if(current_node->out >= 0) {
if (return_str.Pos(Voc_Indexes[current_node->out]) == 0)
{
return_str = return_str + Voc_Indexes[current_node->out];
}
//========== нашли и ищем дальше ===============
callback(words[current_node->out].c_str(), pos - words[current_node->out].length(), pos - 1);
}
}
}
return return_str;
}
private:
struct BorNode
{
BorNode() : fail(NULL), out(-1) {}
map<char, BorNode*> links;
BorNode* fail;
int out;
};
BorNode root;
vector<string> words;
vector<AnsiString> Voc_Indexes;
};
void print(const char* str, int start, int end)
{
//ShowMessage;
//Form1->Memo3->Lines->Add(("Найдено:" + AnsiString(str)/* + " (начало " + IntToStr(start) + ", конец " + IntToStr(end) + ")"*/));
}
//=============== подгружаемс массивы ахокорасивских словарей ===
//vector <AhoCorasick> VOCS_AK;
AhoCorasick VOCS_AK[1000];
void PreloadAhoCorasik()
{
int j=1;
//-------------------------------------------
AnsiString VocIndexes;
//-------------------------------------------
Form1->ProgressBar1->MaxValue = MyPotoks.size();
Form1->ProgressBar1->MinValue = 0;
Form1->Panel6->Visible = true;
//VOCS_AK.clear();
for (int i=0; i<MyPotoks.size();i++)
{
AhoCorasick VOC_AK;
Form1->ProgressBar1->Progress = i;
Form1->lProcent->Caption = "Инициализация по потоку: " + MyPotoks[i].potok_array;
Form1->lProcent->Left = (Form1->Panel6->Width)/2 - (Form1->lProcent->Width)/2;
Application->ProcessMessages();
for (int my_word = 0; my_word < POTOKS_WORDS_OTOBR[i].voc_words.size(); my_word++)
{
VOCS_AK[i].AddString(POTOKS_WORDS_OTOBR[i].voc_words[my_word].c_str(), POTOKS_WORDS_OTOBR[i].world_voc_str[my_word]);
}
//========== Прогресс бар создания общих по потокам словарей ====
VOCS_AK[i].Init();
//VOCS_AK.push_back(VOC_AK);
//VOC_AK.~AhoCorasick();
Form1->ProgressBar1->Progress = i;
Application->ProcessMessages();
}
Form1->Panel6->Visible = false;
}
//===============================================================
//============= Стандартный поиск ========================
//===============================================================
int default_search_func(AnsiString s, AnsiString sub_s)
{
int res = 0;
//===== текст итак должен поступать апперкейховский ===
//s = AnsiUpperCase(s);
res = s.Pos(sub_s);
if (res == 0) return -1; else return res;
}
//=========================================================================================================
//=====================================поиск мура ====================================
//=========================================================================================================
//---------------------------------------------------------------------------
/*
y - строка, в которой искать
x - строка, которую ищем
n - длина y
m - длина х
возвращает -1, если не найдено; в противном случае возвращает
индекс первого вхождения подстроки в строку
*/
//---------------------------------------------------------------------------
unsigned int horspool_search( byte* y , byte* x ,int n , int m )
{
int a, i, j, bm_bc[ ASIZE ];
byte ch, lastch, y1;
//y1 = *y;
/* Preprocessing */
for ( a=0; a < ASIZE; a++ ) bm_bc[ a ] = m;
for ( j=0; j < m-1; j++ ) bm_bc[ x[ j ] ] = m - j - 1;
/* Searching */
lastch = x[ m-1 ];
i = 0;
while (i <= n-m)
{
ch = y[ i + m - 1 ];
if (ch == lastch)
if ( memcmp( &y[ i ], x, m-1 ) == 0 )
return i;
i += bm_bc[ ch ];
}
return -1;
}
//=========================================================================================================
//=========================поиск по выбранному словарю в указанном файле====================================
//=========================================================================================================
AnsiString SearchVocWordsInFile(int PotokNumber, char * tmp_y, DWORD fSize)
{
AnsiString tmpresult = ""; //---ничего не найдено
unsigned long z1 = ::GetTickCount();
tmpresult = VOCS_AK[PotokNumber].Search(tmp_y, print);
unsigned long z2 = ::GetTickCount();
unsigned long z3 = z2-z1;
return(tmpresult);
}
|
| Код |
//===============================================================
//======================= Удаление содержимого каталога =========
//===============================================================
bool DeleteDir(AnsiString DirName, int mode)
{
if ((mode == 1) && (Form1->CheckBoxDeleteCount->Checked == true) && (FilesDeleteCount > Form1->CSpinEditDeleteCount->Value))
{
return false;
}
TSearchRec sr;
if ( DirName.Length() ) {
if (!FindFirst(DirName+"\\*.*",faAnyFile,sr))
do {
if (!(sr.Name=="." || sr.Name=="..")) // это удалять не надо
if (((sr.Attr & faDirectory) == faDirectory ) ||
(sr.Attr == faDirectory)) // найдена папка
{
FileSetAttr(DirName+"\\"+sr.Name, faDirectory ); // сброс всяких
// read-only
DeleteDir(DirName+"\\"+sr.Name, mode); //рекурсивно удаляем содержимое
RemoveDir(DirName + "\\"+sr.Name); // удаляем теперь уже пустую
// папку
}
else // иначе найден файл
{
FileSetAttr(DirName+"\\"+sr.Name, 0); // сброс всяких read-only
DeleteFile(DirName+"\\"+sr.Name); // удаляем файл
FilesDeleteCount++;
}
}
while (!FindNext(sr)); // ищем опять, пока не найдем все
FindClose(sr);
}
return true;
}
//=============================================================
//===============================================================
//========== удаление каталога вместе с содержимым c опциями ====
//===============================================================
void deldir(AnsiString dirname,int mode)
{
/*SHFILEOPSTRUCT sh;
sh.hwnd=Application->Handle;
sh.wFunc = FO_DELETE;
dirname += '\0';
sh.pFrom = dirname.c_str(); //удаляемая директория
sh.pTo = NULL;
sh.fFlags = FOF_NOCONFIRMATION | FOF_SILENT;
sh.hNameMappings = 0;
sh.lpszProgressTitle = NULL;
SHFileOperation(&sh);*/
//DeleteDir(dirname);
FileSetAttr(dirname, 0);
DeleteDir(dirname, mode);
RemoveDir(dirname);
}
|
Ну далее что-то не отправляется сообщение, типа больлшое, в обем остальной код модуля включает лишь неиспользуемые функции не связанные с вышеприведенным кодом..так что как-то так вот Добавлено через 6 минут и 25 секундсам файл
Присоединённый файл ( Кол-во скачиваний: 5 )
SrchWdsInFlsUnit.cpp 13,08 Kb |
Ошибка добавления в вектор - push_back() 
Загрузка ...
