Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Энтропия бинарных комбинаций файла


Автор: Гость_Андрей 5.12.2004, 18:18
Хай, пипл! Есть такая задача: требуется открыть любой файл в бинарном виде и составить по нему словарь. Под словарем следует понимать энтропию комбинаций из 0 и 1. К примеру, Файл=01011110; Словарь: 0(нулей) –3, 1 – 5, 00 – 0, 01 – 2, 10 – 2, 11 – 3… 01011110 –1. Как можно организовать поиск и почему? (файл или char* )(Builder 5)

Автор: manu 5.12.2004, 19:24
А какова наибольшая длина комбинации?
Я думаю тут следует сделать бинарное дерево. Организовать побитовое чтение из файла.
Алгоритм такой:
читаем из файла 1 бит в регистр (при этом ставим бит в начало регистра, а его значение смещаем влево на бит и отрезаем справа по максимальной длине комбинации)
пока файл не закончился:
обновить дерево для комбинации регистр
прочитать бит из файла в регистр.
вывести результаты

обновление дерева выглядит так: смотрим первый бит регистра. если он 0 -- идем в левое поддерево, если 1 -- в правое. если поддерева нет -- создаем новое. увеличиваем количество повторений для узла. сдвигаем регистр на бит в право и повторяем операцию пока в регистре не останется ни одного бита.

Если инетересует конкретная реализация отдельных мест -- пиши, ответимsmile

Автор: Guest 6.12.2004, 15:40
TBits* incWord(TBits *buf, long &lengthWord)
{
//ShowMessage(lengthWord);
for (long l= lengthWord; l>=0; l--)
{
if (buf->Bits[l]==0)
{
buf->Bits[l]=1;
return buf;
}
else
{
buf->Bits[l]=0;
if (l==0)
{
lengthWord++;
buf->Bits[lengthWord]=0;
return buf;
}
};
};
}

void __fastcall TForm1::Open1Click(TObject *Sender)
{
AnsiString NFile;
if (OpenDialog1->Execute()) NFile=OpenDialog1->FileName;
FILE *F;
char name[100];
strcpy(name, NFile.c_str());
if ((F = fopen(name, "rb+")) == NULL)
ShowMessage("Nelza otkrit!");
long curpos, lengthFile;
curpos = ftell(F);
fseek(F, 0L, SEEK_END);
lengthFile = ftell(F);
fseek(F, curpos, SEEK_SET);
byte bRead;
TBits *binBuf= new TBits; //zdelat delete
binBuf->Size = lengthFile * 8;
long i=0;
while (lengthFile)
{
lengthFile--;
fread(&bRead, sizeof(byte), 1, F);
byte bMask = 1 << 7;
for (byte c=1; c<=8; c++)
{
binBuf->Bits[i]= (bRead & bMask ? 1:0);
bMask >>=1;
i++;
};
};
// findWord(binBuf);
TBits *word= new TBits;
long lengthWord=0;
word->Size = binBuf->Size;
word->Bits[lengthWord]=0;
long kolvo=0; // kol-vo raz vstrechaetsya slovo
while (lengthWord < binBuf->Size + 1)
{
//perebor for odnogo slova
for (long i=0; i < binBuf->Size - (lengthWord); i++)
{
for (long j=0; j<=lengthWord; j++)
if (word->Bits[j] == binBuf->Bits[j+i])
{
if (j == lengthWord)
kolvo++;
}
else break;
};
//zapisat kolvo v ?
AnsiString str;
for (long j=0; j<=lengthWord; j++)
{
str+=(word->Bits[j]) ? '1':'0';
};
str+=" ";
str+=kolvo;
Form1->Memo1->Lines->Add(str);
word = incWord(word,lengthWord);
kolvo=0;
};
if (lengthWord == binBuf->Size -1)
{
for (long i=0; i<=lengthWord; i++)
word->Bits[i] = binBuf->Bits[i];
// dlya ostalnih kombinaciy = 0. DOPISAT`!!!
};
delete word;

delete binBuf;
fclose(F);


может так?

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)