Подобные имена

[Igors]

Добрый день

Есть объекты имеющие имена (уникальность не гарантируется)

Код:

emo0003-Base:Hips
emo0003-Base:Spine
emo0003-Base:Spine1
... еще 100 таких

Теперь импортируется файл данных где имеются данные с "подобными" имена

Код

C++ (Qt)
emo0003-Straight walking_Loop_Female:Hips
emo0003-Straight walking_Loop_Female:Spine
emo0003-Straight walking_Loop_Female:Spine1
...
 

Необходимо найти какому объекту соответствуют какие данные файла. Подобная задача была, но здесь как исходные так и файловые данные не обязаны все начинаться с какой-то подстроки (префикса). Также нельзя полагаться что "разделитель" всегда двоеточие как в примере выше. Может быть и подчеркивание и знак мейла - как хотят так и именуют.

Понятно что в общем виде задача не определена, нужны доп указания юзера. Сделал банальный find/replace - предъявляю список данных файла и он может подменять. Работает, но вбивать длинные строки руками не хотят, просят "предложить" варианты чтобы можно было выбрать их из комбика. Т.е. для примера выше в диалоге replace должны по умолчанию появляться строки emo0003-Base и emo0003-Straight walking_Loop_Female. Как это сделать?

Спасибо

[deMax]

Из: emo0003-Base:Hips, emo0003-Base:Spine, emo0003-Base:Spine1... найти наибольшую общую подпоследовательность и убрать её
аналогично со вторым списком. Полученные списки должны совпасть.

Если не совпадают и в строках осталась соль(CRC, мусор...) анализировать строки на похожесть, и удалить соль.

[Racheengel]

А нельзя просто сравнивать строки с конца до двоеточия?
Я так понимаю, это и есть разделитель типа Имя:Тип, нет?
Тогда если "типы" совпали - то выдавать их имена в комбик.

[Igors]

Из: emo0003-Base:Hips, emo0003-Base:Spine, emo0003-Base:Spine1... найти наибольшую общую подпоследовательность и убрать её
аналогично со вторым списком. Полученные списки должны совпасть.

"Подпоследовательность" здесь ни при чем, это чисто "подстрока" (см разницу в ссылке) причем стартовая (префикс). А главное - оба набора могут иметь строки не имеющие никакого отношения к префиксам. И как тогда искать - хз. Напр взяли пару строк, у них разные первые буквы, дальше что? 

А нельзя просто сравнивать строки с конца до двоеточия?
Я так понимаю, это и есть разделитель типа Имя:Тип, нет?

Читаем стартовый пост. Я уж не прошу "внимательно", просто читаем

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

Пока решил считать разделителем любой символ "не буква и не цифра", не вижу лучшего. Разумеется не гарантируется что базовое имя (напр Hips, Spine) само не имеет того же символа.

[Racheengel]

Пока решил считать разделителем любой символ "не буква и не цифра", не вижу лучшего. Разумеется не гарантируется что базовое имя (напр Hips, Spine) само не имеет того же символа.

а можно считать разделителем символ, который встречается в строке ровно 1 раз?

[Igors]

а можно считать разделителем символ, который встречается в строке ровно 1 раз?

Нет

[Racheengel]

Тогда что чисто визуально можно сказать: матчить с конца до первого несовпадения.
Решение простое, но вряд ли будет лучше других.

[Igors]

Извиняюсь что исчез - рубанули инет с 1-го (политика)

Тогда что чисто визуально можно сказать: матчить с конца до первого несовпадения.
Решение простое, но вряд ли будет лучше других.

Это только первый шаг: находим "последнее слово" в каждой строке, структурка

Код

C++ (Qt)
typedef QVector<QStringRef> TRefVec;
typedef QPair<TRefVec, TRefVec> TRefPair;   // вектора строк из первого и второго наборов 
 
QMap<QString, TRefPair> theMap;
 

Напр для строки с концом "Hips" (ключ) значения будут ссылки на строки из обоих наборов (оба вектора не пустые). Это уже "вариант", т.е. замена приведет к совпадению имен  (хотя бы к одному)

А вот что дальше?

[PinkPanther]

Хэширование подстрок всех имен (1-й символ имени, 2 первых символа имени, 3 первых символа имени   ...  все символы имени).
При выборе любого объекта, даже если их миллиард, будет легко расставить элементы противоположного массива в порядке максимального соответствия. Полное соответствие - отлично, на символ меньше - хуже, и т.д. Если соответствие достигнуто по длине левого слова, но правые слова длиннее, то чем больше лишних символов справа, тем хуже.
Результаты хранить в словаре (QSet), словарь для каждого массива, индекс - строка, значение - вектор из указателей на объекты или номеров строк в файле.

Пример: xxxxxxx:Linda1, 27 строка в файле
Добавляем 27 в вектор по индексу L
Добавляем 27 в вектор по индексу Li, если индекса нет, создаем...
И так до Linda1.

Отсечь имя можно регулярным выражением "^.+[^a-zA-Z0-9]([a-zA-Z0-9]+)\s*$"

[Igors]

Пример: xxxxxxx:Linda1, 27 строка в файле
Добавляем 27 в вектор по индексу L
Добавляем 27 в вектор по индексу Li, если индекса нет, создаем...
И так до Linda1.

Отсечь имя можно регулярным выражением "^.+[^a-zA-Z0-9]([a-zA-Z0-9]+)\s*$"

Опять смотрим стартовый пост: конкретный символ-разделитель неизвестен. Уже сейчас неск вариантов: двоеточие, пробел, мейл и подчеркивание. Поэтому полагаем что разделителем может быть любой символ не буква и не цифра

[deMax]

Есть объекты имеющие имена (уникальность не гарантируется)

В строке "emo0003-Base:Hips" текст "emo0003-Base" и разделитель ":" будут для всех объектов одинаковыми?
Т.е. имя объекта можно получить как QString("text%1text").arg(имя_для_поиска) или возможны случаи: big hips / small spine .

[Igors]

В строке "emo0003-Base:Hips" текст "emo0003-Base" и разделитель ":" будут для всех объектов одинаковыми?

В рамках данного файла - да. Для другого файла нет, напр другой создатель может юзать
"emo0003-Base@Hips"

Т.е. имя объекта можно получить как QString("text%1text").arg(имя_для_поиска) или возможны случаи: big hips / small spine .

возможны, не гарантируется что разделитель "используется только как разделитель"

[deMax]

В рамках данного файла - да. Для другого файла нет, напр другой создатель может юзать "emo0003-Base@Hips"

Взять один файл: сравнить первую строку со второй, найти одинаковые начало и конец, а потом эти строки сравнить с третей... получим маску - префикс("emo0003-Base@") + имя("Hips") + суфикс(""). По имени сортировать, или тут что то более хитрое?

В чем сущность разделителя когда текст перед ним всегда одинаковый?

[Igors]

Взять один файл: сравнить первую строку со второй, найти одинаковые начало ...

Опять читаем первый пост

Подобная задача была, но здесь как исходные так и файловые данные не обязаны все начинаться с какой-то подстроки (префикса). 

... и конец

В одном файле концы строк вряд ли совпадут, ведь это имена объектов без префикса. Но могут быть пары с одинаковыми концами в 2 файлах

Просьба отвечать более вдумчиво, а не так, "лепить лепуху". Спасибо за понимание

[deMax]

Хотелось бы формализовать задачу, потому что пока не очень понятны входные данные и какие формы они могут принять.
Я правильно понял: есть список объектов, имя состоит из %random_string%separator%name и нам надо найти %separator(который уникален для файла) -> потом находим имя -> поиск? (маску найти тоже легко)
или у нас более общая задача есть 2 списка %random_string%name и найти соответствия элементов?

Может пример приведете самого общего случая? Или правило по которому это имя может сформировано?
так как из этого:

emo0003-Base:Hips
emo0003-Base:Spine
emo0003-Base:Spine1

имя извлечь элементарно