Алгоритм разбора и сопоставления строк - PullRequest
Новая
       14

Алгоритм разбора и сопоставления строк

3 голосов
/ 27 января 2012

Я решаю следующую проблему:

Предположим, у меня есть список пакетов программ, и их имена могут выглядеть следующим образом (единственное известное, что эти имена сформированы как SOMETHING + VERSION, что означает, что версия всегда приходит после имя) : 

Efficient.Exclusive.Zip.Archiver-PROPER.v.122.24-EXTENDED
Efficient.Exclusive.Zip.Archiver.123.01
Efficient-Exclusive.Zip.Archiver(2011)-126.24-X
Zip.Archiver14.06
Zip-Archiver.v15.08-T
Custom.Zip.Archiver1.08
Custom.Zip.Archiver1

Теперь мне нужно проанализировать этот список и выбрать только последние версии каждого пакета. Для этого примера ожидаемый результат будет: 

Efficient-Exclusive.Zip.Archiver(2011)-126.24-X
Zip-Archiver.v15.08-T
Custom.Zip.Archiver1.08

Текущий подход, который я использую, можно описать следующим образом: 

Split the initial strings into groups by their starting letter,
ignoring spaces, case and special symbols.
(`E`, `Z`, `C` for the example list above)

Foreach element {

    Apply the regular expression (or a set of regular expressions),
    which tries to deduce the version from the string and perform
    the following conversion `STRING -> (VERSION, STRING_BEFORE_VERSION)`

    // Example for this step:
    // 'Efficient.Exclusive.Zip.Archiver-PROPER.v.122.24-EXTENDED' ->
    // (122.24, Efficient.Exclusive.Zip.Archiver-PROPER)

    Search through the corresponding group (in this example - the 'E' group)
    and find every other strings, which starts from the 'STRING_BEFORE_VERSION' or
    from it's significant part. This comparison is performed in ignore-case and
    ignore-special-symbols mode.

    // The matches for this step:
    // Efficient.Exclusive.Zip.Archiver-PROPER, {122.24}
    // Efficient.Exclusive.Zip.Archiver, {123.01}
    // Efficient-Exclusive.Zip.Archiver, {126.24, 2011}

    // The last one will get picked, because year is ignored.

    Get the possible version from each match, ***pick the latest, yield that match.***

    Remove every possible match (including the initial element) from the list.
}

Этот алгоритм (как я предполагаю) должен работать для чего-то вроде O(N * V + N lg N * M), где M обозначает среднее время сопоставления строк, а V обозначает рабочее время регулярного выражения версии.

Тем не менее, я подозреваю, что есть лучшее решение (всегда есть!) , возможно, конкретная структура данных или лучший подход к сопоставлению.

Если вы можете что-то предложить или , сделайте несколько заметок о текущем подходе , пожалуйста, не стесняйтесь делать это.

Ответы [ 2 ]

2 голосов
/ 27 января 2012

Как насчет этого?(Псевдокод) 

Dictionary<string,string> latestPackages=new Dictionary<string,string>(packageNameComparer);

foreach element
{
    (package,version)=applyRegex(element);

    if(!latestPackages.ContainsKey(package) || isNewer)
    {
        latestPackages[package]=version;
    }
}

//print out latestPackages

Операции со словарем - это O (1), поэтому у вас есть O (n) общего времени выполнения.Предварительная группировка не требуется, и вместо сохранения всех совпадений вы сохраняете только тот, который является самым новым.

Словарь имеет конструктор, который принимает объект IEqualityComparer.Там вы можете реализовать свою собственную семантику равенства между именами пакетов.Имейте в виду, однако, что вам нужно реализовать метод GetHashCode в этом IEqualityComparer, который должен возвращать те же значения для объектов, которые вы считаете равными.Чтобы воспроизвести приведенный выше пример, вы можете вернуть хеш-код для первого символа в строке, который будет воспроизводить группировку, которая была у вас внутри словаря.Однако вы получите большую производительность благодаря более умному хеш-коду, в котором не так много коллизий.Возможно использование большего количества символов, если это все еще дает хорошие результаты.

1 голос
/ 27 января 2012

Я думаю, что вы, вероятно, могли бы использовать DAWG (http://en.wikipedia.org/wiki/Directed_acyclic_word_graph) здесь для хорошего эффекта. Я думаю, что вы могли бы просто циклически сокращать каждый узел, пока не дойдете до того, у которого есть только 1 «дочерний». На этом узле у вас будет общийпрефиксы "вверх" вверх по дереву и строкам версий ниже. Отсюда разбираем строки версий, удаляя все, что не является цифрой или точкой, разделяя строку по периоду и конвертируя каждый элемент массива в целое число.дать вам массив int для каждой строки версии. Определите самую высокую версию, запишите ее и перейдите к следующему узлу только с одним дочерним элементом.

РЕДАКТИРОВАТЬ: заполнение большой DAWG - довольно дорогая операция, но поиск очень быстрый.

...