Как объединить похожие элементы в списке

Question

Я не нашел ничего релевантного в Google, поэтому надеюсь найти здесь какую-нибудь помощь:)

У меня есть список Python следующим образом:

[['hoose', 200], ["Bananphone", 10], ['House', 200], ["Bonerphone", 10], ['UniqueValue', 777] ...]

У меня есть функция, которая возвращает расстояние Левенштейна между 2 строками, для Хауса и Хоуза она возвращает 2 и т. Д.

Теперь я хочу объединить элементы списка, у которых показатель Левенштейна равен f.e. <5, пока (!) Добавляю свои баллы, поэтому для результирующего списка хочу следующее: </p>

[['hoose', 400], ["Bananaphone", 20], ['UniqueValue', 777], ...]

или

[['House', 400], ["Bonerphone", 20], ['UniqueValue', 777], ...]  

и т.д.

Это не имеет значения, пока их значения добавляются.

В списке будет только 2 предмета, которые очень похожи, поэтому эффект цепочки любого предмета, похожего на множество других, пожирающих их все, не ожидается.

Answer 1

Чтобы пояснить смысл моего комментария, я просто взял реализацию этого расстояния от здесь и вычислил несколько расстояний:

d('House', 'hoose') = 2
d('House', 'trousers') = 4
d('trousers', 'hoose') = 5

Теперь предположим, что ваш порог равен 4. Вы должны объединить House и hoose, а также House и trousers, но не trousers и hoose , Вы уверены, что подобное может никогда не случиться с вашими данными?

В конце концов, я думаю, что это скорее проблема кластеризации, поэтому вам, вероятно, придется изучить алгоритмы кластеризации. SciPy предлагает реализацию иерархической кластеризации , которая работает с пользовательскими функциями расстояния (имейте в виду, что это может быть очень медленно для больших наборов данных - это также потребляет много памяти).

Основная проблема заключается в выборе меры для качества кластера, потому что нет единственного правильного решения вашей проблемы. Эта статья (pdf) дает вам отправную точку для понимания этой проблемы.

Answer 2

Как и в случае с другими комментариями, я не уверен, что делать это имеет смысл, но вот решение, которое делает то, что вы хотите, я думаю.Это очень неэффективно - O (n ² ) где n - количество слов в вашем списке - но я не уверен, что есть лучший способ сделать это:

data = [['hoose', 200],
        ["Bananphone", 10],
        ['House', 200],
        ["Bonerphone", 10],
        ['UniqueValue', 777]]

already_merged = []

for word, score in data:
    added_to_existing = False
    for merged in already_merged:
        for potentially_similar in merged[0]:
            if levenshtein(word, potentially_similar) < 5:
                merged[0].add(word)
                merged[1] += score
                added_to_existing = True
                break
        if added_to_existing:
            break
    if not added_to_existing:
        already_merged.append([set([word]),score])

print already_merged

Вывод:

[[set(['House', 'hoose']), 400], [set(['Bonerphone', 'Bananphone']), 20], [set(['UniqueValue']), 777]]

Одна из очевидных проблем этого подхода состоит в том, что рассматриваемое вами слово может быть достаточно близко ко многим различным наборам слов, которые вы уже рассмотрели, но этокод просто объединит его с первым найденным кодом.Я проголосовал +1 за ответ Space_C0wb0y ;)

Answer 3

import Levenshtein
import operator
import cluster

class Item(object):
    @classmethod
    def fromList(cls,lst):
        return cls(lst[0][0], lst[0][1], lst[1])

    def __init__(self, name, val=0, score=0):
        super(Item,self).__init__()
        self.name     = name
        self.val      = val
        self.score    = score

    def dist(self, other):
        return 100 if other is self else Levenshtein.distance(self.name, other.name)

    def __str__(self):
        return "('{0}', {1})".format(self.name, self.val)

def main():
    myList = [
        [['hoose', 5], 200],
        [['House', 5], 200],
        [["Bananaphone", 5], 10],
        [['trousers', 5], 100]
    ]
    items = [Item.fromList(i) for i in myList]

    cl = cluster.HierarchicalClustering(items, (lambda x,y: x.dist(y)))
    for group in cl.getlevel(5):
        groupScore = sum(item.score for item in group)
        groupStr   = ', '.join(str(item) for item in group)
        print "{0}: {1}".format(groupScore, groupStr)

if __name__=="__main__":
    main()

возвращает

10: ('Bananaphone', 5)
500: ('trousers', 5), ('hoose', 5), ('House', 5)

Answer 4

@ Mark Longair Я получил некоторые ошибки в Python 3.5, поэтому я исправил их, как показано ниже:

import Levenshtein
data = [['hoose', 200],
       ["Bananphone", 10],
       ['House', 200],
       ["Bonerphone", 10],
       ['UniqueValue', 777]]

already_merged = []

for word, score in data:
    added_to_existing = False
    for merged in already_merged:
        for potentially_similar in merged[0]:
            if Levenshtein.distance(word, potentially_similar) < 5:
                merged[0].add(word)
                merged[1] += score
                added_to_existing = True
                break
        if added_to_existing:
            break
    if not added_to_existing:
        already_merged.append([set([word]),score])

print (already_merged)

@ Марк, спасибо за такое простое решение.

Answer 5

Вы не сказали количество элементов в вашем списке, но я предполагаю, что n ^ 2 сложность в порядке.

Вы также не сказали, хотите ли вы сравнить все возможные пары или только соседние. Я предполагаю все пары.

Так вот идея:

1. Возьмите первый предмет и посчитайте левую оценку по всем остальным предметам.
2. Объедините все предметы, которые набрали менее 5 баллов, удалив их из списка и суммировав их баллы.
3. В объединенном списке возьмите следующий элемент, сравните его со всеми элементами, кроме того, который вы только что отметили.
4. Повторяйте, пока в списке нет элементов

Answer 6

Чертеж:

result = dict()
for item in [[['hoose', 5], 200], [['House', 5], 200], [["Bananaphone", 5], 10], ...]:

   key = item[0] # ('hoose', 5)
   value = item[1] # 200

   if key in result:
       result[key] = 0
   result[key] += value

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