The OpenNET Project / Index page

[ новости /+++ | форум | wiki | теги | ]

форумы  помощь  поиск  регистрация  майллист  ВХОД  слежка  RSS
"Поиск и получение подстроки в одинаковой для двух и более ст..."
Вариант для распечатки  
Пред. тема | След. тема 
Форумы Программирование под UNIX (Public)
Изначальное сообщение [Проследить за развитием треда]

"Поиск и получение подстроки в одинаковой для двух и более ст..."  
Сообщение от lightspeed (ok) on 11-Фев-06, 22:57 
Приветствую тебя, All
Поиск и получение подстроки одинаковой для двух и более строк.
Известно, что подстрока одинаковая для всех строк - единственная одинаковая подстрока.
Ищу наименее затратный по процессорному времени (не по памяти) алгоритм.
Сделал в тупую, разбирая первую строку и проверяя каждую ее подстроку с другими строками. Не удовлетворяет производительность.
Можно-ли это сделать с помощью grep/egrep кода?
Пока, не могу ничего нормального придумать...
:(
Правка | Высказать мнение | Ответить | Cообщить модератору | Наверх

 Оглавление

Сообщения по теме [Сортировка по времени, UBB]


1. "Поиск и получение подстроки в одинаковой для двух и более ст..."  
Сообщение от rWizard email(??) on 12-Фев-06, 00:48 
можете привести пример разбираемого файла и того, что нужно получить?
(если много, можно на почту )


Правка | Высказать мнение | Ответить | Cообщить модератору | Наверх

2. "Поиск и получение подстроки в одинаковой для двух и более ст..."  
Сообщение от lightspeed (ok) on 12-Фев-06, 04:13 
>можете привести пример разбираемого файла и того, что нужно получить?
>(если много, можно на почту )

Вот пример. Допустим есть строка:
$text = "text не text1, опять text1 и снова text3.";
мне нужно получить слово text1. Повторяющееся два раза в тексте.
Знаки препинания не важны.

я делаю так:
if ($text =~ /([0-9A-Za-z]+) +\1/) { print "found: $1\n"; }

И это работает, если text1 повторяется подряд. Но, если он стоит в разных частях строки, то, данный regexp не обнаруживает повторения.
И это не понятно почему, т.к. он должен запоминать контент.

Правка | Высказать мнение | Ответить | Cообщить модератору | Наверх

3. "Поиск и получение подстроки в одинаковой для двух и более ст..."  
Сообщение от jd (??) on 12-Фев-06, 07:10 
Не совсем понял задачу, но судя по примеру вам поможет что-то вроде (если нужно именно на perl):
if ($text =~ /(?:^|\W)(\w+)\W.*(?<=\W)\1(?:\W|$)/) { print "found: $1\n"; }
Конечно, нужно учесть, что \w - это не совсем то, что было в вашем примере. Он включает ещё '_'. А \W, соответственно, не включает...
Правка | Высказать мнение | Ответить | Cообщить модератору | Наверх

4. "Поиск и получение подстроки в одинаковой для двух и более ст..."  
Сообщение от jd (??) on 12-Фев-06, 07:14 
Ну и, как справедливо замечено в книжке "Регулярные выражения" (неточное цитирование): всегда нужно учитывать контекст задачи. Вполне может оказаться, что это выражение можно уполовинить.
Правка | Высказать мнение | Ответить | Cообщить модератору | Наверх

5. "Поиск и получение подстроки в одинаковой для двух и более ст..."  
Сообщение от lightspeed (ok) on 12-Фев-06, 12:01 
>Ну и, как справедливо замечено в книжке "Регулярные выражения"
>(неточное цитирование): всегда
>нужно учитывать контекст задачи. Вполне может оказаться, что это выражение можно
>уполовинить.

Да, это примерно то, что нужно.
А теперь вопрос, как получить некую матрицу, где по вертикали слова найденные в совпадении, а по горизонтали количество совпадений данного слова? Т.е. задача понимания некоего текста, основанная на статистическом подсчете количества совпадений. А затем сравнение данных совпдадений с некоей строкой поиска. Чем выше количество совпадений, тем выше статус данного текста для данной строки поиска.
Пример: Google.
Используя данный алгоритм можно получить 1-е совпадение. А как с оставшимися словами, совпадающими в тексте далее?

Правка | Высказать мнение | Ответить | Cообщить модератору | Наверх

6. "Поиск и получение подстроки в одинаковой для двух и более ст..."  
Сообщение от Wulf on 12-Фев-06, 16:48 
> Используя данный алгоритм можно получить 1-е совпадение. А как с оставшимися словами, совпадающими в тексте далее?

Вы сразу задачу полностью ставьте. В первоначальном посте Вам требовалось нахождение longest common subsequence (lcs), которую опеннетовские велосипедостроители сразу предложили решить принципиально нерабочим методом (перловый регексовый конечный автомат находит первое совпадение, а не ищет совпадение с максимальной длиной, как это делает posix-овский). Вместе с тем эта задача полностью изъедена 30 лет назад и тучу готовых алгоритмов с анализом, описаниями и кодом можно отыскать в гугле по вышеупомянутым трем словам.
Потом у вас все изменилось и оказалось, что нужно multiple-patterns string matching. Т.е. несколько другое. В этом случае, как я понимаю, вам надо рыть в сторону алгоритма Ахо-Корасика (Aho Corasik)

P.S. Прошу прощения за излишнее употребление англ. терминов

Правка | Высказать мнение | Ответить | Cообщить модератору | Наверх

7. "Поиск и получение подстроки в одинаковой для двух и более ст..."  
Сообщение от Wulf on 12-Фев-06, 16:58 
> которую опеннетовские велосипедостроители сразу предложили решить принципиально нерабочим методом
Извиняюсь перед человеком под  ником jd, которого я по ошибке назвал "велосипедостроителем", недостаточно внимательно просмотрев тред. Он всего-лишь поправил чужой код. Велосипедостроитель, конечно, здесь автор темы.
Правка | Высказать мнение | Ответить | Cообщить модератору | Наверх

8. "Поиск и получение подстроки в одинаковой для двух и более ст..."  
Сообщение от lightspeed (ok) on 13-Фев-06, 00:21 
>> которую опеннетовские велосипедостроители сразу предложили решить принципиально нерабочим методом
>Извиняюсь перед человеком под  ником jd, которого я по ошибке назвал
>"велосипедостроителем", недостаточно внимательно просмотрев тред. Он всего-лишь поправил чужой код. Велосипедостроитель,
>конечно, здесь автор темы.

Ну велосипедостроитель, или не велосипедостроитель, мне понадобился алгоритм, и вы мне дали. За, что вам спасибо. Как спасибо и jd, за то, что он подправил мой код.
:)

Кстати Wulf. Прочтите еще раз мой первый топик. Что я просил? Правильно, алгоритм, для того что-бы _не_ строить свой собственный велосипед.
Понимаете?

А то, что я все-го лишь попытался развить алгоритм jd, до моей второй задачи. Ну что-же, мне надо было попробывать.
Кстати, и алгоритм jd мне тоже очень пригодился.
:)

Т.ч. не стоит говорить про изобретательство. Или попросту говоря "наезжать". Здесь собираются, в основном специалисты. И пусть я ранее не слышал про этот алгоритм, это совсем ничего не значит.
Т.к. возможны вы не слышали, про другие вещи, в которых разбираюсь я.
:)

Правка | Высказать мнение | Ответить | Cообщить модератору | Наверх

9. "Поиск и получение подстроки в одинаковой для двух и более ст..."  
Сообщение от lightspeed (ok) on 13-Фев-06, 00:23 
Кстати, не извиняйтесь за английский.
Поверьте, здесь собирается образованный народ.
:)

С уважением,
Сергей

Правка | Высказать мнение | Ответить | Cообщить модератору | Наверх

Архив | Удалить

Индекс форумов | Темы | Пред. тема | След. тема
Оцените тред (1=ужас, 5=супер)? [ 1 | 2 | 3 | 4 | 5 ] [Рекомендовать для помещения в FAQ]




Спонсоры:
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2020 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру