Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Perl: Общие вопросы > Алгоритм поиска

Автор: zuk 20.3.2007, 14:35

Доброго времени суток.

Если кто сталкивался, дайте совет.
Есть задача: найти наибольшее последовательное совпадение знаков (цифр) строки со знаками (цифрами) других строк. Например, есть файл в формате .dbf, в котором очень!!! много строк содержащих цифры (до 11 цифр в каждой строке (но заранее не известно сколько).  И есть шаблон из определенного кол-ва цифр. Надо найти в файле строку, кот наиболее совпадала бы с шаблоном.

Пр.

шаблон 111111987

строки в файле
......
112434
123424
111123
111111   здесь наибольшее совпадение
111211
...........

а может быть и так

...........
111198
111217
234
342455657
3434
1111112
1111118
11111197
11111198  здесь наибольшее совпадение
232
344
...........

Строки в файле НЕ упорядочены. Повторяю, в файле очень!!! много строк (поэтому возникает еще один вопрос, эффективна ли перед поиском сортировка, ведь она тоже займет время). Нужен наиболее быстрый алгоритм поиска.

Автор: Nab 20.3.2007, 15:20

если именно такова задача, то сортировка поможет однозначно раз, и алгоритм без сортировки, приблизительно такой:

Код


# считываем данные
my @array = <file>;
# счетчик строк
my $i = 0;
# шаблон
my $pattern = 111111987;
# результат
my ($len, $idx) = (0, -1);


foreach (@array) {
  # Ищем не шаблон внутри строк а строки внутри шаблона
  #  сохраняем и длину и номер строки в которой было совпадение 
  # если мы нашли в шаблоне одну из строк и она длиннее предыдущего совпадения
  if ($pattern =~ /$_/ and length > $len) {
    $len = length;
    $idx = $i ;
  }
  $i++
}

print "Наибольшее совпадение в ".$idx." строке ".$array[$idx] if $idx >= 0;

писал прям в форум так что за опечатки не взыщите..

Автор: zuk 20.3.2007, 15:45

Благодарю, но является ли это наиболее эффективным алгоритмом. Здесь идет простая переборка всего файла. Сортировку массива, я думаю можно осущесвить средствами foxpro. Но это надо будет делать через интерфейс на perl. Кстати, может кто посоветовать подходящий модуль для работы с foxpro. Почему нужна эффективность и скорость, кол-во строк может превышть десятки и сотни тысяч. Для начала, я как понимаю их надо выгрузить все в массив, а потом вести поиск.

Автор: Nab 20.3.2007, 17:27

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

Алгоритм же я указал, что просто линейный, по отсортированному массиву искать совсем по другому надо. Но отсортированный массив, все одно потребует минимум единичного прохода по всему массиву. Его изначально нужно привести в упорядоченный вид.
Если же вы собрались сортировать при каждом акте поиска, то это еще вдвое-втрое увеличит необходимость в ресурсах, как памяти так и времени... так что уж лучше линейным поиском.
Так вот алгоритм которым нужно будет искать зависит именно от того как он будет отсортирован, простым списком, или индексами в dbf, или еще как... может средствами модуля XBase это можно сделать...

Автор: zuk 20.3.2007, 17:52

Я не издеваюсь, Nab. Просто задача только поиском не ограничена. Там нужно будет сделать еще кое-какую работу. Можно, конечно, запрограммировать все это средствами foxpro, но мне показалось, что perl будет удобнее. Ваше мнени, что для такого объема информации perl лучше не использовать? С Гигобайтом памят, сколько примерно займет времени на поиск в файле с 30 тысячами строк (максимально)?

Автор: Nab 20.3.2007, 18:01

Я вам не предлагаю реализовывать на foxpro, я вам предлагаю не мешать оба продукта, а выбрать из них что-то одно, иначе вы врядли получите какой либо выиграш ...

Ну 30 тысяч, это не так уж и много smile

по скорости конкретно даже представить не могу. Я не знаю скоростных параметров модуля XBase в перле, и не знаю на сколько потолстел Foxpro после нашего последнего общения с ним. Также это зависит от общей структуры данных в dbf, от индексации... не думаю что там только одно поле с такими данными...

Автор: zuk 20.3.2007, 18:10

Я не хочу мешать и то и другое, я хочу все реализовать на perl. Просто файл в формате dbf. Так значит все таки perl хорошее для этого орудие? Я в нем не сомневался smile

. И наиболее эффективным способом Вы счиатете переборку значений, пока не будет найдено совпадение?

Автор: nitr 20.3.2007, 22:37

zuk, с FoxPro-таблицами прекрасно работает как Delphi, C++, Perl и многие другие, думаю у вас Винда, значит поставить драйвер ODBC для оного smile

и будет прекрасная поддержка, выбирать язык... Можно выбирать данные из таблиц (а dbf ни что иное smile

) с помощью небезызвестного SQL, простыми запросами ;)

Зачем обрабатывать dbf иначе? Можно ли эту ситуацию "в студию" smile

Незнание FoxPro или его отсутствие или что-то другое, не проблема smile

Perl... "я огромный его поклонник", но что-то невижу +ов ;) особенно если будет и некая "клиентская часть". Да понимаю можно реализовать веб-интерфейс, но многи понравиться? smile

Автор: amg 21.3.2007, 08:32

zuk, вот такой простейший линейный алгоритм работает, как мне кажется, достаточно быстро. Проверял на файле из 100_000 ~ 15-значных чисел, созданном такой командой:

Код


perl -le 'print rand for 1..1e5' | sed 's/^0\.//' > file

Скрипт тратит на обработку массива 0.2-0.3 с. На более коротких файлах/строках будет, разумеется, быстрее. Кстати, на сортировку такого массива уходит больше времени (а сортировка в Perl весьма эффективна). Так что, наверное, сортировать не стоит.

Код


open F, 'file' or die;
@a = <F>; chomp @a;
$pattern = reverse '12345678';

$i = $max_count = $max_i = 0;
$max_str = '';
foreach (@a) {
  $pat = $pattern;
  $str = reverse $_;
  $i++;
  $count = 0;
  $count++ while ($pat && $str && chop($pat) eq chop($str));
  if ($count > $max_count) {
    $max_count = $count;
    $max_i = $i;
    $max_str = $_;
  }
}
close F;
print "$max_str $max_i $max_count\n";

Использовал связку reverse-chop: здесь где-то есть пост, в котором выяснили, что это быстрейший способ последовательного получения символов строки.
Если есть опасение, что файл не будет влазить в память, то можно foreach (@a) {} заменить на while (<F>) {}, суммарное время (с учетом зачитывания файла в массив) будет даже меньше.

Автор: nitr 21.3.2007, 11:24

Для работы с табличками FoxPro примерчик даю:

Код


#!perl
use strict; use warnings;
use DBI;
use CGI::Carp qw(fatalsToBrowser);

my $dsn = 'DRIVER=Microsoft FoxPro VFP Driver (*.dbf);UID=;Deleted=Yes;Null=Yes;Collate=Machine;BackgroundFetch=Yes;Exclusive=No;SourceType=DBF;SourceDB=D:\DBF'; #Указываем каталог D:\DBF , где лежат наши таблички,-файлы dbf

my $dbh = DBI->connect("dbi:ODBC:$dsn", '', '', { PrintError => 1, RaiseError => 1 } );

my $sth = $dbh->prepare('SELECT * FROM `FILENAME.DBF`'); #Указывать .DBF необязательно
$sth->execute;
while (my $row = $sth->fetchrow_arrayref) {
    print join("\t", @$row)."\n";
}

а вот сами драйвера тут - http://msdn2.microsoft.com/en-us/vfoxpro/bb190233.aspx

Добавлено @ 11:32
З.Ы.: и почему-то на Делфи работало быстрее ;) хе хе, или у меня таблицы большие ;), zuk не ответил о клиентской части, если конечно он просто тренируется, типа обучается перлу, то другое, а если это работа, то мой совет был уже дан не в пользу перла :(

Добавлено @ 11:35
Но у меня работа с ODBC...

Автор: nitr 21.3.2007, 11:45

Проверил с модулем DBD::XBase:

Код


#!perl
use strict; use warnings;
use DBI;

my $dbh = DBI->connect('dbi:XBase:.', '', '', { PrintError => 1, RaiseError => 1 } ) or die $DBI::errstr;

my $sth = $dbh->prepare('SELECT * FROM R050506.DBF') or die $dbh->errstr();
$sth->execute;
while (my $row = $sth->fetchrow_arrayref) {
    print join("\t", @$row)."\n";
}

тот же результат по времени smile

Добавлено @ 11:58
Разница двух методов:
1 - выдаёт в виндовой кодировке cp1251
2 - в кодировке таблицы, в моём случае cp866

Автор: nitr 21.3.2007, 12:03

Второй всё же быстрее, даже если перекодировку сделать в другую... smile

Но всё же медленее Delphi+ADO.
XBase подходит особенно для *nix smile

, так что если требуется сделать на перл работу с dbf, используй этот Драйвер http://search.cpan.org/~janpaz/DBD-XBase-0.241/lib/DBD/XBase.pm

Автор: zuk 21.3.2007, 17:40

Добрый вечер.

Это для работы. GUI (если это подразумевалось под клиентсокй частью), в принципе, не самое важное. Если надо, простейший интерфейс можно реализовать на Tk.

Суть задачи после поиска. Найдя соответсвие, вычисляем разницу в кол-ве знаков. Далее, раскрываем число (добавляем к найденному цифры), но при этом на минимальное кол-во знаков. Вобщем пример.

111111789 - шаблон

111111 - найденное

надо

1111110
1111111
1111112
1111113
1111114
1111115
1111116
11111170
11111171
11111172
...............
111111780
111111781
111111782
111111283
.................
111111789 - здесь надо добавить строку в другое поле таблицы (но это можно реализоваь в любом месте)
11111179
1111118
1111119

Теперь стало яснее. Таблица состоит из нескольких столбцов. Но поиск придется вести по одному (о кот и идет речь). Я думаю перебирать значение в нем, например, fetch_arrow и сравнивать. Выгружать все в массив я думаю нет смысла. Так реализовать поиск. Использовать модуль xbase. ОС Винда. Конечный файл должен быть преобразованный начальный, то есть тоже dbf.

Завтра выложу то,что получилось.
Спасибо за участие))

Автор: nitr 21.3.2007, 22:07

Цитата(zuk @ 21.3.2007, 17:40

)

Выгружать все в массив я думаю нет смысла. Так реализовать поиск.

где ты в моём примере нашёл это? smile

это раз, а два - реализовать проще с DBI-DBD::XBase-запросами SQL. Данный модуль вообще не зависит от ОС.

А как работать с файлом dbf иначе... имхо чушь ;)

Автор: tishaishii 23.3.2007, 21:39

Посмотри модуль String::Approx.

Автор: tishaishii 23.3.2007, 22:14

Когда-то я разработал алгоритм для поиска наиболее точных шаблонов для многих строк.

Рассмотрим на 2х, т.к. писать много, но работает для многих.
Есть строки A="abckd" и B="dacbdaf".
Представляешь строки в виде массивов символов, нумеруешь каждый символ.
Составляешь матрицу типа:

Код

        1    2    3    4    5
        a    b    c    k    d
1    d    0    0    0    0    1
2    a    1    0    0    0    0
3    c    0    0    1    0    0
4    b    0    1    0    0    0
5    d    0    0    0    0    1
6    a    1    0    0    0    0
7    f    0    0    0    0    0

Т.е., например, A по горизонтали, B - по вертикали.
1 - совпадение символов в строках, 0 - сам понимаешь.

Удаляешь все строки и столбцы (с номерами), в которых нет единиц. Нумерацию символов обязательно сохраняешь.

Код

        1    2    3    5
        a    b    c    d
1    d    0    0    0    1
2    a    1    0    0    0
3    c    0    0    1    0
4    b    0    1    0    0
5    d    0    0    0    1
6    a    1    0    0    0

Рассматриваешь получившуюся матрицу посимвольно с точки зрения A. Получается, что A(1)="a" принадлежит B(2, 6), A(2) принадлежит B(4), ...
Т.е. строишь списки:

Код

1:{2,6}
2:{4}
3:{3}
5:{1,5}

Т.е., по-синтаксису выше, A(i):{B(j[k[u]])}, а, по-математике, A(i) принадлежит {B(j[k[u]])}.
Вот надо искать самые длинные списки таких B[j[k[u]]], что B[j[k[u]]]<B[j[k[u+1]]].
Ну, сложно выразился. Посмотри глазами. Надо, чтобы позиция каждой предыдущей буквы из B была меньше следующей.

Посмотри глазами (ещё раз).
Предполагаемое ре

Добавлено @ 22:25
Глюк темплейта форума, не могу редактировать сообщение.
Ошибка в формулировке:

Цитата

Если строк много, то следует пересмотреть всевозможные варианты без повторов пар строк.

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