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

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

Пр.

шаблон 111111987

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

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

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

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

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


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

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

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

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

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

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

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

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

zuk, с FoxPro-таблицами прекрасно работает как Delphi, C++, Perl и многие другие, думаю у вас Винда, значит поставить драйвер ODBC для оного  и будет прекрасная поддержка, выбирать язык... Можно выбирать данные из таблиц (а dbf ни что иное  ) с помощью небезызвестного SQL, простыми запросами ;)

Зачем обрабатывать dbf иначе? Можно ли эту ситуацию "в студию" 
Незнание FoxPro или его отсутствие или что-то другое, не проблема 

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

Это сообщение отредактировал(а) nitr - 20.3.2007, 22:39

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

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

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

Это сообщение отредактировал(а) amg - 21.3.2007, 08:38

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

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

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

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

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

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

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

Второй всё же быстрее, даже если перекодировку сделать в другую...  Но всё же медленее Delphi+ADO.
XBase подходит особенно для *nix  , так что если требуется сделать на перл работу с dbf, используй этот Драйвер DBD::XBase

Это сообщение отредактировал(а) nitr - 21.3.2007, 12:06

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

Это для работы. 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. 

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

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

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

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