Архивировано

Эта тема находится в архиве и закрыта для публикации сообщений.

SmirnoFFx

Методы быстрого поиска строки в БОЛЬШОМ файле

Рекомендованные сообщения

Доброго времени суток, господа!

 

Никак не могу правильно решить проблему поиска строки в файле большого размера.

 

Есть файл с содержанием:

слово1	  слово2	  слово3
слово4	  слово5	  слово6
слово7	  слово8	  слово9
слово10	слово11	слово12
.....			.....		   .....

Необходимо по введенному слову найти остальные n (в настоящем примере две) записи, находящиеся, например, на одной строке (считать, что в файле нет специальных символов перехода на новую строку, т.е. все слова записываются последовательно через определенный интервал).

 

Я использую последовательный поиск:

  1. считал первое слово (слово1)
  2. проверил на совпадение
  3. если не совпадает, пропустил n байт и считал слово 4
  4. проверил на совпадение
  5. если совпадает, считал слово5 и слово6
  6. закончил работу

Но, если файл очень большого размера, а искомая строка находится в конце файла, то последовательный поиск длится очень долго.

 

Подскажите, как можно реализовать механизм быстрого поиска по файлу большого размера...

 

Спасибо. Готов ответить на все, необходимые для решения проблемы, вопросы.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Алгоритмы Бойера-Мура и Кнута-Морриса-Пратта тебе в помощь.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
Алгоритмы Бойера-Мура и Кнута-Морриса-Пратта тебе в помощь.

 

Алгоритм Кнута — Морриса — Пратта:

int seek_substring_KMP (char s[], char q[])
{
int i, j, N, M;
N = strlen(s);
M = strlen(q);
int *d =(int*)malloc(M*sizeof(int)); /* динамический массив длины М*/
/* Вычисление префикс-функции */
i=0;
j=-1;
d[0]=-1;
while(i<M-1)
	{
	while((j>=0) && (q[j]!=q[i]))
		j = d[j];
	i++;
	j++;
	if(q[i]==q[j])
		d[i]=d[j];
	else
		d[i]= j;
	}
/* поиск */
for(i=0,j=0;(i<N)&&(j<M); i++,j++)
	while((j>=0)&&(q[j]!=s[i]))
		j=d[j];
free (d); /* освобождение памяти массива d */
if (j==M)
	return i-j;
else /* i==N */
	return -1;
}

 

Но проблема в том, что поиск должен осуществляться в файле.

 

Поэтому вопрос: как адаптировать данный алгоритм к возможности поиска подстроки в файле?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
Алгоритмы Бойера-Мура и Кнута-Морриса-Пратта тебе в помощь.

 

Алгоритм Кнута — Морриса — Пратта:

int seek_substring_KMP (char s[], char q[])
{
int i, j, N, M;
N = strlen(s);
M = strlen(q);
int *d =(int*)malloc(M*sizeof(int)); /* динамический массив длины М*/
/* Вычисление префикс-функции */
i=0;
j=-1;
d[0]=-1;
while(i<M-1)
	{
	while((j>=0) && (q[j]!=q[i]))
		j = d[j];
	i++;
	j++;
	if(q[i]==q[j])
		d[i]=d[j];
	else
		d[i]= j;
	}
/* поиск */
for(i=0,j=0;(i<N)&&(j<M); i++,j++)
	while((j>=0)&&(q[j]!=s[i]))
		j=d[j];
free (d); /* освобождение памяти массива d */
if (j==M)
	return i-j;
else /* i==N */
	return -1;
}

 

Но проблема в том, что поиск должен осуществляться в файле.

 

Поэтому вопрос: как адаптировать данный алгоритм к возможности поиска подстроки в файле?

А какая собственно разница. Вам же файл все равно надо сначала считать в память

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
Алгоритмы Бойера-Мура и Кнута-Морриса-Пратта тебе в помощь.

 

Алгоритм Кнута — Морриса — Пратта:

int seek_substring_KMP (char s[], char q[])
{
int i, j, N, M;
N = strlen(s);
M = strlen(q);
int *d =(int*)malloc(M*sizeof(int)); /* динамический массив длины М*/
/* Вычисление префикс-функции */
i=0;
j=-1;
d[0]=-1;
while(i<M-1)
	{
	while((j>=0) && (q[j]!=q[i]))
		j = d[j];
	i++;
	j++;
	if(q[i]==q[j])
		d[i]=d[j];
	else
		d[i]= j;
	}
/* поиск */
for(i=0,j=0;(i<N)&&(j<M); i++,j++)
	while((j>=0)&&(q[j]!=s[i]))
		j=d[j];
free (d); /* освобождение памяти массива d */
if (j==M)
	return i-j;
else /* i==N */
	return -1;
}

 

Но проблема в том, что поиск должен осуществляться в файле.

 

Поэтому вопрос: как адаптировать данный алгоритм к возможности поиска подстроки в файле?

А какая собственно разница. Вам же файл все равно надо сначала считать в память

 

А как верно считать файл в память?

 

Делаю так:

FILE *p;
 char *a;

 a = (char*)malloc(1000*sizeof(char));

 p = fopen("C:\\1.dat", "rb");
 fread(a, sizeof(char), 1000, p);

 fclose(p);

//  ShowMessage(strlen(a));

 

ShowMessage(strlen(a)); показывает, что считывается только первые 98 символов. Почему?? Как же считать, например первые 1000 знаков из файла?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

так файл то структуирован, ну и используйте потоковые методы, вроде cin cout

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
так файл то структуирован, ну и используйте потоковые методы, вроде cin cout

Спасибо за совет. Попробую)

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах