Найти последовательности слов в подсписках в Python - PullRequest
Новая
       3

Найти последовательности слов в подсписках в Python

0 голосов
/ 04 июня 2018

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

    [['Start', 'двигаться', 'другая', 'сторона', 'света', 'надолго', 'скоро'], 
     ['Start', 'двигаться', 'другая', 'сторона', 'света', 'чтобы', 'посмотреть'],
     ['Start', 'двигаться', 'новая', 'планета'],
     ['Start', 'двигаться', 'сторона', 'признание', 'суверенитет', 'израильский'],
     ['Start', 'двигаться', 'сторона', 'признание', 'высот', 'на'],
     ['Start', 'двигаться', 'сторона', 'признание', 'высот', 'оккупировать'],
     ['Start', 'двигаться', 'сторона', 'признание', 'высот', 'Голанский'],
     ['Start', 'двигаться', 'сторона', 'признание', 'и']]

Мне нужен алгоритм для поиска двух или более элементов, которые являются общими для двух илиеще составить список и составить из них отдельный элемент.в моем примере 'Start', 'двигаться' является общим для всех элементов, поэтому он должен стать одной строкой.'сторона', 'света', 'надолго' является общим для двух элементов, поэтому оно становится одной строкой.'сторона', 'признание' обычно для 5 элементов, поэтому он становится одной строкой.Если не осталось общих элементов, просто добавьте остальные элементы как одну строку.Желаемый результат: 

    [['Start двигаться', 'другая сторона света', 'надолго скоро'], 
     ['Start двигаться', 'другая сторона света', 'чтобы посмотреть'],
     ['Start двигаться', 'новая планета'],
     ['Start двигаться', 'сторона признание', 'суверенитет израильский'],
     ['Start двигаться', 'сторона признание', 'высот на'],
     ['Start двигаться', 'сторона признание', 'высот оккупировать'],
     ['Start двигаться', 'сторона признание', 'высот Голанский'],
     ['Start двигаться', 'сторона признание', 'и']]

До сих пор я пробовал несколько циклов и сравнение элементов: 

for elem,next_elem in zip(lst, lst[1:]+[lst[0]]):
    if elem[0] == next_elem[0] and elem[1] == next_elem[1] and elem[2] == next_elem[2]:
        elem[0:3] = [' '.join(elem[0:3])]

    if elem[0] == next_elem[0] and elem[1] == next_elem[1]:
        elem[0:2] = [' '.join(elem[0:2])]

Но я не думаю, что это правильный путь.Наборы также не являются опцией, поскольку в подсписке может быть несколько вхождений одного элемента.Я проверил другие темы LCS, но не нашел решения.Любой работающий алгоритм, который делает работу, будет великолепен, эффективность в данный момент не важна.Еще несколько примеров: 

[[a,b,c,d],
 [a,b,d,e,f]]

Должен стать: 

[[ab,cd],
 [ab,def]]

Поскольку a,b являются общим элементом, а cd, def просто становятся одним элементом. 

[[a,b,c,d,e,g],
[a,b,c,d,g,h],
[a,b,h,h,i]]

Должно стать: 

[[ab,cd,eg],
 [ab,cd,gh],
 [ab,hhi]]

Поскольку ab и cd являются пушкой для двух или более подсписков

А: 

[[a,b,c],
 [a,b,d]]

Становится: 

[[ab, c],
 [ab, d]]

Так как c, d не являются общими элементами

Ответы [ 2 ]

0 голосов
/ 04 июня 2018

Вы можете начать с создания префиксного дерева , представляющего ваши списки: 

lists = [['Start', 'двигаться', 'другая', 'сторона', 'света', 'надолго', 'скоро'], 
         ['Start', 'двигаться', 'другая', 'сторона', 'света', 'чтобы', 'посмотреть'],
         ['Start', 'двигаться', 'новая', 'планета'],
         ['Start', 'двигаться', 'сторона', 'признание'],
         ['Start', 'двигаться', 'сторона', 'признание', 'суверенитет', 'израильский'],
         ['Start', 'двигаться', 'сторона', 'признание', 'высот', 'на'],
         ['Start', 'двигаться', 'сторона', 'признание', 'высот', 'оккупировать'],
         ['Start', 'двигаться', 'сторона', 'признание', 'высот', 'Голанский'],
         ['Start', 'двигаться', 'сторона', 'признание', 'и']]

tree = {}
end = "END"
for lst in lists:
    d = tree
    for x in lst:
        d = d.setdefault(x, {})
    d[end] = {}

Результат (здесь END отмечает, где закончилось предложение): 

{'Start': {'двигаться': {'другая': {'сторона': {'света': {'надолго': {'скоро': {'END': {}}},
                                                          'чтобы': {'посмотреть': {'END': {}}}}}},
                         'новая': {'планета': {'END': {}}},
                         'сторона': {'признание': {'END': {},
                                                   'высот': {'Голанский': {'END': {}},
                                                             'на': {'END': {}},
                                                             'оккупировать': {'END': {}}},
                                                   'и': {'END': {}},
                                                   'суверенитет': {'израильский': {'END': {}}}}}}}}

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

def join(d, pref=[]):
    if end in d:
        yield [' '.join(pref)] if pref else []
    for k, v in d.items():
        if len(v) == 1:
            for x in join(v, pref + [k]): # add node to prefix
                yield x                   # yield next segment
        else:
            for x in join(v, []):         # reset prefix
                yield [' '.join(pref + [k])] + x # yield node + prefix and next

Выходные данныене точно , как в вашем вопросе, но очень близко.Он объединит все части, которые имеют только один дочерний элемент в дереве, т. Е. Впоследствии сегменты должны быть максимальными, в то время как ни один сегмент не является частью более длинного сегмента. 

>>> for x in join(tree):
...     print(x)
...
['Start двигаться', 'другая сторона света', 'надолго скоро']
['Start двигаться', 'другая сторона света', 'чтобы посмотреть']
['Start двигаться', 'новая планета']
['Start двигаться', 'сторона признание']
['Start двигаться', 'сторона признание', 'суверенитет израильский']
['Start двигаться', 'сторона признание', 'высот', 'на']
['Start двигаться', 'сторона признание', 'высот', 'оккупировать']
['Start двигаться', 'сторона признание', 'высот', 'Голанский']
['Start двигаться', 'сторона признание', 'и']

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

enter image description here

0 голосов
/ 04 июня 2018

Я предлагаю вам использовать ключ hashmaps: word, value: Integer в качестве счетчика, начинается с 0. (Это словарь в python).Для каждой строки хешируйте каждое значение и увеличивайте счетчик.В конце, для каждого слова со счетчиком 2 или более, вы объединяете их.

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

...