форумы  помощь  поиск  регистрация  майллист  ВХОД  слежка

Вариант для распечатки		Пред. тема | След. тема
Форумы Программирование под UNIX (Public)
Изначальное сообщение		[Проследить за развитием треда]

"Поиск и получение подстроки в одинаковой для двух и более ст..."

Сообщение от lightspeed (ok) on 11-Фев-06, 22:57

Приветствую тебя, All Поиск и получение подстроки одинаковой для двух и более строк. Известно, что подстрока одинаковая для всех строк - единственная одинаковая подстрока. Ищу наименее затратный по процессорному времени (не по памяти) алгоритм. Сделал в тупую, разбирая первую строку и проверяя каждую ее подстроку с другими строками. Не удовлетворяет производительность. Можно-ли это сделать с помощью grep/egrep кода? Пока, не могу ничего нормального придумать... :(

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

Сообщения по теме

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

1. "Поиск и получение подстроки в одинаковой для двух и более ст..."

Сообщение от rWizard (??) 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]