Совпадение 2 списков строк по внешнему виду - PullRequest
Новая
       7

Совпадение 2 списков строк по внешнему виду

3 голосов
/ 08 апреля 2011

Задача

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

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

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

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

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

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

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

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

Вопрос

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

Где я сейчас нахожусь

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

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

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

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

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

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

Ответы [ 2 ]

2 голосов
/ 08 апреля 2011

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

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

0 голосов
/ 08 апреля 2011

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

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 ++.

...