IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Работа с текстовыми файлами, Удаление повторяющихся слов из файла
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


Суть задачи такая.
Нужно удалить из текстового файла повторяющиеся слова. Причем текстовый файл очень большой, порядка 200 000 строк и повторяющихся слов там тоже очень много smile.gif
Пример
мама
папа
мама
бабушка
дед
мама
Результат должен быть
мама
папа
бабушка
дед

Может это уже решалось здесь, но честное слово искал около часа. Находил тока работу с символами. Хотя может это и почти одно и тоже.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Решение включает в себя две основных задачи:
1. составление словаря;
2. поиск по словарю.

Поскольку размер словаря может быть весьма немалым, и заранее он неизвестен, то желательно использовать динамическую память. При указанном количестве строк и колличество слов может значительно превышать возможности сегмента (64К), так что придется структурировать. Если использование ТР не обязательно, то рекомендую взять 32-битный сомпилятор (например, FPC). Структурирование все равно весьма желательно для ускорения работы и уменьшения размеров. Структура базы данных (словаря) может быть как самой простой (слова в одном массиве of char, разделенные пробелами в алфавитном порядке), так и более сложной Например, блоки описанной струтуры, пронумерованные буквами - или парами, тройками букв.

Вот наглядная иллюстрация сказанного:

1-й способ (1):
а агат аз азот астра аська береза боб бор бочка вода воск восток дед дело дочь дочка

2-й способ с нумерацией одной буквой (2):
!а ? гат з зот стра ська !б ереза об ор очка !в ода оск осток !д ед ело очь очка

2-й способ с нумерацией двумя буквами (3):
1а ? 2г ат 2з ? от 2с тра ька 1б 2е реза 2о б р чка 1в 2о да ск сток 1д 2е д ло 2о чь чка

"?" означает слово без продолжение, только из нумерующих букв. Реально этот знак не нужен - два пробела подряд выполняют его роль.

Даже на глаз видно, что (2) выигрывает по объему по сравнению с (1).
Способ (3) на первый взгляд и сложнее, и места больше требует. Про сложность спорить не буду, но выигрыш в месте там будет заметен при бОльшем размере словаря.

Вот, примерно так.. Выбирай, что нарвится smile.gif. Или предложи свою реализацию..

Да, еще про поиск.. Его можно вести дихотомией с самого начала - либо можно хранить карту пронумерованных блоков. Внутри блока - дихотомия.. smile.gif

Ну, а само удаление слов - дело несложное.. ломать - не делать! smile.gif))))

PS
Уточни также, что считать разделителями слов. Надеюсь, только пробелы..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Цитата
Если использование ТР не обязательно, то рекомендую взять 32-битный сомпилятор (например, FPC)
И тогда задача будет решаться в несколько строк, ибо TStringList + Duplicates
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(volvo @ 1.05.2007 11:15) *

И тогда задача будет решаться в несколько строк, ибо TStringList + Duplicates

smile.gif
Ну, скажем так: я имел в виду подмножество FPC, примерно равное TP, за исключением сквозной адресации памяти. То есть сам язык, а не библиотеки.. Мне это кажется разумным при изучении языка - мало смысла в том, чтоб извращаться с двадцатибитной адресацией типа сегмент-смещение.. Хотя, опрекделенный смысл, конечно, есть - и пусть автор темы решает этот вопрос сам (с помощью препа, полагаю.. smile.gif ).


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


Цитата(Lapp @ 1.05.2007 6:51) *

PS
Уточни также, что считать разделителями слов. Надеюсь, только пробелы..


Разделителем является enter.

Lapp smile.gif после твоего ответа я почуствовал себя тормозом.
Мое решение, то есть пока идея, такова
Создать новый файл и копировать туда слова.
берем новое слово и ищем его во втором файле, если нет, то записываем, иначе берем следующие слово из первого файла smile.gif

Зы: как я понял обращатся к определенному участку текстового файла нельзя?? или можно, если можно подскажите плиз функцию или процедуру, которая это делает
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Цитата
как я понял обращатся к определенному участку текстового файла нельзя


Нельзя ...



--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


Цитата
Еще думаю если исключить вариант с доп. файлом, выгоднее использовать структуру типа списка


sad.gif такое я не проходил, мона небольшой пример
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Упс а я это убрал уже ибо про массивы ни слова не было ...

Примеров куча: Поиск + Все о динамических структурах данных.


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Цитата
Мое решение, то есть пока идея, такова
Создать новый файл и копировать туда слова.
Это реально только для очень небольших файлов... Чем больше файл, и чем больше в нем НЕповторяющихся слов, тем дольше ты будешь проходить по новому файлу в попытке найти текущее слово из исходного файла... Я сейчас запустил написанную по этому алгоритму программу с файлом на 300000 слов , из которых около 50000 - уникальны... Уже 3 минуты, а обработано только около 40000 слов...

Все-таки придется скорее всего работать с динамическими структурами...

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Хм, если словарь не большой (не много разных слов), то все достаточно быстро работает ...

генирируем большой файл
const
n = 10;
count = 200000;

Strings: array [0..n - 1] of String =
(
'mama', 'papa', 'dedushka', 'babushka', 'probabushka',
'sestra', 'brat', 'tesha', 'test', 'zat'

);

file_name = 'large.txt';

var
f: text;
i: LongInt;

begin
assign(f, file_name); rewrite(f);
randomize;

for i := 1 to count do writeln(f, Strings[Random(10)]);

writeln('Done'); close(f);
end.


Сама программа

uses crt;
const
file_name = 'large.txt';

type
PList = ^TList;
TList = record
data: String;
next: PList;
end;

var
f: Text;
head, T, H: PList;
s: String;
begin
assign(f, file_name); reset(f);

if not(eof(f)) then begin
readln(f, s);
new(T);
T^.data := s;
T^.next := nil;
head := T;
end;

while not(eof(f)) do begin
readln(f, s);

H := head;
while (head^.next <> nil) and (head^.data <> s) do head := head^.next;

if (head^.next = nil) and (head^.data <> s) then begin
new(T);
T^.data := s;
T^.next := nil;
head^.next := T;
end;

head := H;
end;

rewrite(f);

while (head <> nil) do begin
T := head;
writeln(f, head^.data);
head := head^.next;
dispose(T);
end;

close(f);
end.


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Ну, со словарем из 10 слов естественно - ограничений по памяти никаких нет, тут все просто... А вот если размеры словаря зашкаливают за 2-3 тысячи, тут придется уже серьезно подумать...

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


да .. сгенерил файл с рандомными словами, и прога ушла в себя nea.gif


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гость






Программа, написанная с использованием списков (деревья дадут гораздо большую скорость при поиске), отработала за 118 сек. против 49 минут по предыдущему алгоритму (слов в исходном файле - 347621, в алфавите - 24000 слов)

uses list;

var
arr_list: array['A' .. 'Z'] of tlist;

function is_present(var lst: tlist; s: string): boolean;
var st: string;
begin
is_present := lst.present(s);
end;

var
f_in, f_out: text;
s: string;
T: dword;
count_n, count_unique: integer;

ch: char;

begin
for ch := 'A' to 'Z' do begin
arr_list[ch].init;
end;

assign(f_in, 'very_big.txt');
reset(f_in);

assign(f_out, 'very_dup.txt');
rewrite(f_out);

count_n := 0; count_unique := 0;
while not eof(f_in) do begin
readln(f_in, s);
inc(count_n);
if count_n mod 50 = 0 then writeln(':: read ', count_n);

if not is_present(arr_list[upcase(s[1])], s) then begin
writeln(f_out, s);
inc(count_unique);
arr_list[upcase(s[1])].append(s);
end;
end;
close(f_out);
close(f_in);
writeln('count = ', count_n, ' unique = ', count_unique);

for ch := 'A' to 'Z' do begin
arr_list[ch].done;
end;

end.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15





Группа: Пользователи
Сообщений: 4
Пол: Мужской

Репутация: -  0  +


Мой пример кода, как и говорил volvo работает офигеть, как долго

Uses Crt;

Var
s,st:string;
f1,f2:text;
x:INTEGER;
label a;
Begin

assign(f1,'C:\Pascal\zadachi\pere-ka\words2.txt');reset(f1);
assign(f2,'C:\Pascal\zadachi\pere-ka\words3.txt');

while not eof(f1) do
begin
while not eoln(f1) do
begin
read(f1,s);{Читаем слово из первого файла}
end;
readln(f1);
reset(f2);
while not eof(f2) do
begin
while not eoln(f2) do
begin
read(f2,st); {Читаем слова из второго файла}
if s=st then {Проверяем, есть ли совпадения}
begin
inc(x);
goto a;
end;
end;
readln(f2);
end;
a:
append(f2);
if x=0 then writeln(f2,s);{если совпадения не было,
записываем слово во второй файл (f2)}
x:=0;
end;
close(f1);
close(f2);
end.


Поэтому буду разбиратся с динамическими структурами.

Зы: по поводу словаря. как упорядочить слова в словаре? по буквам?
пока тока идея попробывать с преобразованием букв в числа, и по этому методу упорядочить.

ЗЗЫ: to volvo. есть одна загвоздка, слова все русские, то есть написаны на киррилице. и поэтому массив [A..Z] не очень пригодится sad.gif а массив [А..Я] не работает yes2.gif

Сообщение отредактировано: dened -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Гость






Цитата
есть одна загвоздка, слова все русские, то есть написаны на киррилице
Это решается довольно просто:

{ Пишешь функцию, корректно работающую с кириллицей }
Function UpCase(ch: char): char;
Begin
UpCase := ch;
Case s[i] Of
'a' .. 'z': Upcase := Chr(Ord(s[i])-$20);
#160 .. #175: Upcase := Chr(Ord(s[i])-$20);
#224 .. #239: Upcase := Chr(Ord(s[i])-$50)
End;
End;

{ Перечисляешь весь алфавит }
const
alpha = 'АБВГД...'; { перечислен весь алфавит - 32 буквы }
var
arr_list: array[1 .. 32] of tlist;

...
for i := 1 to 32 do begin
arr_list[i].init;
end;
...

{ и работаешь вот в таком ключе: }
if not is_present(arr_list[pos(upcase(s[1]), s)], s) then begin ...



P.S. Кстати,
Цитата
а массив [А..Я] не работает
- это как понимать? Проверить не могу, но работать должно, особенно с учетом приведенной выше функции Upcase... Множество символов 'А' .. 'Я' - неразрывно, ничего лишнего в нем не содержится... Почему ты решил, что оно не работает, и как именно "не работает"?

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 21:12
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name