Сопоставьте 2 списка строк по сходству

Проблема

У меня есть 2 списка строк. Я хочу найти самые подходящие пары из моих списков.

Например, у меня есть эти 2 списка:

list1 = {"a1","b1","c1"}
list2 = {"a2","b2","c2"}

Я хочу получить следующие результаты:

results = {{"a1,"a2"}, {"b1,"b2"}, {"c1,"c2"}}

Дополнительная информация

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

Я усложняюсь, когда разные пары получают одинаковые результаты расстояния. Вы не можете просто взять минимальное расстояние для определенного элемента в list1, потому что другой элемент в list1 может получить такое же расстояние с тем же элементом в list2.

Вопрос

У вас есть предложения алгоритмов для этого?

Где я сейчас

Вам лучше сначала не смотреть на мои находки, чтобы моя работа не повлияла на вас.

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

  • пара (индексы i, j в моем двумерном массиве)
  • расстояние

Затем я сортирую этот массив, используя элемент расстояния.

Наконец, я просматриваю отсортированный массив и определяю элементы с общим расстоянием вместе (сначала все расстояния == 0, затем все расстояния == 1 и т. д.). Каждый раз, когда я разрешаю элемент, я помечаю его в своем 2D-массиве, поэтому я могу быстро пропустить разрешенные элементы в моем отсортированном массиве.

Я думаю, что могу лучше, чем это решение. Он может быть не самым эффективным во времени и пространстве.


list string matching algorithm
person decasteljau    schedule 07.04.2011    source источник
comment
Пожалуйста, определите лучшее соответствие. Сумма расстояний? Сумма квадратов расстояний?   -  person biziclop    schedule 08.04.2011
comment
Если вы хотите минимизировать сумму расстояний, ваша проблема, по-видимому, заключается в максимально взвешенном двудольном сопоставлении, если это поможет.   -  person biziclop    schedule 08.04.2011
comment
@biziclop очень интересный вопрос. Я не видел такой проблемы. Я не уверен, что будет лучше: сумма расстояний или сумма квадратов. Я исследую эти пути. Спасибо   -  person decasteljau    schedule 08.04.2011

Ответы (2)


arrow_upward
2
arrow_downward

После того, как вы установили метрику, которую хотите использовать для отслеживания «расстояния» между двумя строками, будь то расстояние Левенштейна или другое, вы можете использовать Венгерский алгоритм для решения вашей проблемы.

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

person abeln    schedule 08.04.2011
comment
Изучив комментарии, оставленные biziclop, я нашел этот алгоритм, который идеально подходит для моей проблемы. спасибо! - person decasteljau; 08.04.2011
comment
Примечание: венгерский алгоритм работает и дает хорошие результаты, однако показывает серьезную проблему с производительностью. Алгоритм O (N ^ 3), и при использовании с сотнями записей его обработка может быстро стать очень долгой. - person decasteljau; 11.04.2011
comment
Из любопытства, сколько это сотен записей: 200, 300, ...? - person abeln; 11.04.2011
comment
Я обнаружил, что производительность сильно зависит от контента. Когда совпадения легко найти (идеальные совпадения или близкие совпадения с низким уровнем неоднозначности), производительность очень хорошая. Но когда вы передаете совершенно несвязанные списки, содержащие всего 100 записей, производительность катастрофическая (например, 30+ секунд). Надеюсь, для меня нормальным случаем являются списки, которые хорошо совпадают. - person decasteljau; 12.04.2011
comment
Хм... O(n^3) со 100 записями, занимающими 30+ секунд. Конечно, в O-нотации скрыта довольно большая константа. - person abeln; 12.04.2011
comment
Я обнаружил, что проблемы с производительностью связаны с использованием STL в отладке. Тот же сценарий, занимающий 30 секунд в DEBUG, занимает менее 100 мс в сборке Release. - person decasteljau; 13.04.2011
comment
Рад слышать, что вы смогли ускорить процесс! - person abeln; 13.04.2011

arrow_upward
0
arrow_downward

Мое предложение по возможной оптимизации:

I calculate the Levenshtein distance for each possible pair of string and store the results in a 2-dimension array.

В том, что вы можете избежать вычисления расстояния для каждой возможной пары строк, учитывая их длину. Потому что скажем:

1. if the pair is e.g. "ab", and "cdefg"
2. and you know that there's another string that has similar length with "ab" e.g. "xy"

Тогда вам не нужно вычислять расстояние между «ab» и «cdefg». Потому что минимальное расстояние, которое вы можете получить между строками такой длины, равно 3, тогда как максимальное расстояние между двумя строками одинаковой длины ("ab" и "xy", как в примере) будет равно 2.

Вы можете сделать это, используя более интеллектуальную структуру данных, которая отслеживает длину строк, например. unordered_map<int, vector<string> > в C++0x или tr1 C++.

person ryaner    schedule 07.04.2011