Общий паттерн нескольких строк

← →
sdubaruhnul (2007-09-16 14:06) [0]

Нужно найти общий паттерн в нескольких строках, которые представляют собой имена файлов. Что конкретно подразумевается? Например, есть файлы:

test1_file1.txt
test2_file2.txt
test3_filesome.txt

Общим паттерном здесь будет строка test$1_file$2. Соответсвенно, символ $ - дело конвенциональное. И, скажем, $N - это только строка, т.е. не выделяю числа.

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

← →
Anatoly Podgoretsky © (2007-09-16 14:14) [1]

> sdubaruhnul (16.09.2007 14:06:00) [0]

Если сделать XOR то нулевые символы будут представлять собой совпадающую часть.

← →
sdubaruhnul (2007-09-16 14:19) [2]

>Если сделать XOR то нулевые символы будут представлять собой совпадающую часть

Это слишком частное решение. Несовпадающие части могут быть разными по длине.

← →
Сергей М. © (2007-09-16 14:27) [3]

> Несовпадающие части могут быть разными по длине

Что мешает привести "подопытные" строки к единой (максимальной из имеющихся) длине, дополнив их при необходимоости, скажем, пробелами ?

← →
Anatoly Podgoretsky © (2007-09-16 14:32) [4]

> sdubaruhnul (16.09.2007 14:19:02) [2]

Нет никакой необходимости делать это по разной длине, это 100% несовпадение, надо нормализовывать перед исполнением. Даже обычные сравнения строк сразу отсекаются по длине, как несовпадающие.

← →
Anatoly Podgoretsky © (2007-09-16 14:32) [5]

> Сергей М. (16.09.2007 14:27:03) [3]

К минимальной?

← →
Сергей М. © (2007-09-16 14:34) [6]

> Anatoly Podgoretsky © (16.09.07 14:32) [5]

Да, конечно к минимальной.
Эт я в другую крайность проглючил)

← →
sdubaruhnul (2007-09-16 14:37) [7]

Э-э, народ, вы не в ту степь поехали. Сформулирую задачу по-другому. Есть строки:

string123_hello123 stringTEST_helloTEST

Они попадают под wildcard маску string*_hello*. Вот эту маску мне и хотелось бы получить. При этом строк может быть более двух.

← →
Anatoly Podgoretsky © (2007-09-16 14:47) [8]

> sdubaruhnul (16.09.2007 14:37:07) [7]

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

← →
sdubaruhnul (2007-09-16 15:13) [9]

>Это уже другой вопрос, не совпадающий с первым

Можно подробнее? В чём отличие?

← →
Sha © (2007-09-16 15:20) [10]

1. Даешь определение общий паттерн
2. Даешь определение максимальный общий паттерн.
3. Решаешь задачу оптимизированным перебором (метод ветвей и границ)

← →
sdubaruhnul (2007-09-17 13:39) [11]

Блин, как только запахло чем-то большим, чем xor, Мастера самоудалились.

← →
Anatoly Podgoretsky © (2007-09-17 18:32) [12]

> sdubaruhnul (17.09.2007 13:39:11) [11]

О на слабо пытаешь брать, как правило результат противоположный.

← →
sdubaruhnul (2007-09-17 18:59) [13]

>О на слабо пытаешь брать, как правило результат противоположный.

А я уже не надеюсь, поэтому констатирую. А вы, Анатолий, не могли бы ответить на [9]?

← →
Anatoly Podgoretsky © (2007-09-17 19:20) [14]

> sdubaruhnul (17.09.2007 18:59:13) [13]

Я тебе уже сказал, что это сложная задача, по сравнению с первой постановкой.
И очень ресурсоемкая. Тратить силы на решение не интерсной для меня задачи не считаю возможным.

← →
sdubaruhnul (2007-09-17 19:32) [15]

>Anatoly Podgoretsky © (17.09.07 19:20) [14]

Анатолий, вы читать умеете? В номере 9 я спрашиваю, чем постановка в [0] отличается от постановки [7]?

← →
Anatoly Podgoretsky © (2007-09-17 19:39) [16]

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

← →
Sha © (2007-09-17 20:30) [17]

> sdubaruhnul (17.09.07 13:39) [11]
> Блин, как только запахло чем-то большим, чем xor, Мастера самоудалились.

По элгоритмам решения экстремальных задач много чего написано
в умных книжках всякими разными авторами. Тебе лень читать?

← →
Anatoly Podgoretsky © (2007-09-17 20:32) [18]

Термин хороший :-)

← →
sdubaruhnul (2007-09-17 22:11) [19]

Anatoly Podgoretsky © (17.09.07 19:39) [16]

>А в первой постановке сравнение посимвольное.

Можно ключевое слово в первом посте, из которого следует, что сравнение посимвольное?

>По элгоритмам решения экстремальных задач много чего написано
в умных книжках всякими разными авторами. Тебе лень читать?

Спасибо за то, что определили эту задачу как экстремальную.

Всяких разных авторов читать не хочу. Конкретных можете назвать?

← →
sdubaruhnul (2007-09-17 22:12) [20]

Вторая часть поста предназначалась для Sha © (17.09.07 20:30) [17]

← →
Anatoly Podgoretsky © (2007-09-17 23:30) [21]

> sdubaruhnul (17.09.2007 22:12:20) [20]

Он четко назвал как эта задача называется.

← →
Германн © (2007-09-18 00:47) [22]

> Можно ключевое слово в первом посте, из которого следует,
> что сравнение посимвольное?

Ключевого слова может и нет, но пример приведен неудачный.
В отличие от [7]

> string123_hello123
> stringTEST_helloTEST
>
>
> Они попадают под wildcard маску string*_hello*

пример в [0] подпадает под маску string?_hello*. А это вполне нормально решаемая задача. Задача же [7] как принято говорить "общего аналитического решения" не имеет. Но, как и известная "задача трёх тел" вполне может иметь одно или несколько "частных решений".
Если тебя твоя задача интересует в смысле общего решения, то трать на нее годы сам. Если - частного, озвучь практический смысл этой задачи.

← →
Германн © (2007-09-18 00:56) [23]

> Anatoly Podgoretsky © (17.09.07 20:32) [18]
>
> Термин хороший :-)
>

Хороший, но не совсем правильный. Экстремальность - это, имхо, практическая сторона решения. А тут, опять же имхо, либо тупость, либо (скорее всего) "партизанство" © АП
:-)

P.S.
На мысль о "партизанстве" меня навела строка из сабжа
> Нужно найти общий паттерн в нескольких строках, которые
> представляют собой имена файлов.

А зачем "нужно" не сказано?

> sdubaruhnul (17.09.07 22:11) [19]
> Всяких разных авторов читать не хочу. Конкретных можете назвать?

Хорошиая, книга, но есть ошибки в алгоритмах:
Романовский И.В. - Алгоритмы решения экстремальных задач

Или ищи в инете "метод ветвей и границ" - это твой случай.

← →
sdubaruhnul (2007-09-18 17:57) [25]

>Sha © (18.09.07 01:22) [24]

OK, спасибо.

>Германн © (18.09.07 00:56) [23]

>А зачем "нужно" не сказано?

А это уже идея, которую я не хочу выдавать. Но для вас исключение.

Удобное переименовывание файлов. Например, у меня есть группа файлов:

01. Paul Van Dyke - Beautiful Place (Airwaves Mix).mp3
02. Paul Van Dyke - Beautiful Place (Paradise Mix).mp3
...

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

Путь 1. Выделяем все файлы, Ctrl+R, пишем "Paul Van Dyke" исправить на "Paul van Dyk".

Путь 2 - Путь сдубарухнувшего (The way I am!). Выделяем все файлы, жмём Ctrl+Q, появляется текстовое поле примерного содержания

$1. Paul Van Dyke - Beautiful Place ($2).mp3

которое я исправляю на

$1. Paul van Dyk - Beautiful Place ($2).mp3

жму пипку Enter и вся группа файлов изменяется.

Увижу где эту идею - прокляну.

> [25] sdubaruhnul (18.09.07 17:57)

А вот эта штука - TRegExpr не поможет тебе?

>{RASkov}
Регулярные выражения работают с текстом по маске.
А тут нужно к нескольким тесктам подобрать общую маску.

> sdubaruhnul (18.09.07 17:57) [25]

Вариант 1. На основании введенного шаблона строить регулярное выражение, согласно которому видоизменять оставшиеся удовлетворяющие ему имена. Предусмотреть наиболее вероятные варианты.

Вариант 2. Выявляем измененную часть по оригинальному имени и введенному шаблону. Заменяем выявленную часть во всех остальных именах не затрагивая остального.

Придирка:

> sdubaruhnul (18.09.07 17:57) [25]
> 01. Paul Van Dyke - Beautiful Place (Airwaves Mix).mp3
> 02. Paul Van Dyke - Beautiful Place (Paradise Mix).mp3
> Я вижу, что какой-то плохой человек неправильно
> написал название исполнителя и это нужно исправить.

Да, внимательностью я никогда не отличался, увы.
Не могу найти тут различий в имени исполнителя. :(

> Увижу где эту идею - прокляну.

Гы :)
Супер-пупер мега идея как всегда.

← →
sdubaruhnul (2007-09-20 18:23) [30]

>Да, внимательностью я никогда не отличался, увы.(

Это точно.

>Не могу найти тут различий в имени исполнителя. :

Зайди на Discogs и найди отличие.

← →
webpauk (2007-09-20 20:13) [31]

> sdubaruhnul (16.09.07 14:06)

интересная задача
завтра попробую решить

> Увижу где эту идею - прокляну.

Total commander, Переименование группы файлов :)
Кристиану Хислеру место в аду обеспечено :)

Замена подстроки StringReplace

А вообще по моему это задача для регулярных выражений.

← →
sdubaruhnul (2007-09-27 22:13) [33]

>Arm79 © (21.09.07 15:31) [32]

Спасибо, я качал 15 мб, чтобы убедиться, что такой функциональности, которую я хочу сделать, там нет. Автор Тотала может не беспокоиться, а своё "по моему это задача для регулярных выражений" надо превратить в уверенное "это не задача для регулярных выражений".

Общий паттерн нескольких строк Найти похожие ветки