Как найти похожие слова в списке?

Question

[pcdesign]

Есть такой список
['голубец', 'конь', 'голубцы', 'лист']
Программа должна выдать: голубец

Еще пример:
['стол', 'день', 'свет', 'клинок', 'светильник']
Программа должна выдать: свет.

Ну и еще пример:
['восток', 'дань', 'исток', 'жир', 'голубь', 'да']
Программа должна выдать: восток

Как это реализовать на python?

Answer 1

[Andrey Dugin]

# -*- coding: utf-8 -*-

from difflib import SequenceMatcher
from itertools import combinations, imap

def ratio(pair):
    return (SequenceMatcher(None, *pair).ratio(), pair[0])

def findword(wordlist):
    pairs = combinations(wordlist, 2)
    found = max(imap(ratio, pairs))[1] 
    return found

print findword(['голубец', 'конь', 'голубцы', 'лист'])
print findword(['стол', 'день', 'свет', 'клинок', 'светильник'])
print findword(['восток', 'дань', 'исток', 'жир', 'голубь', 'да'])

Результат:

голубец
свет
восток

Comments

[pcdesign]

Спасибо! Красивое у вас решение.

[pcdesign]

Пытаюсь ваше решение вставить в реальный проект, но vim выдает предупреждение.
Ну то есть не ошибка, а типа не соответствует канонам:

"E731 do not assign a lambda expression, use a def [pep8]"
stackoverflow.com/questions/25010167/e731-do-not-a...

[Andrey Dugin]

def ratio(pair): return (SequenceMatcher(None, *pair).ratio(), pair[0])

Answer 2

[pcdesign]

Ну как-то вот так получилось:

import difflib


def similar(arr):
    s = difflib.SequenceMatcher()
    full = []
    for i in arr:
        s.set_seq2(i)
        for n in (arr):
            if n == i:
                continue
            s.set_seq1(n)
            full.append((s.ratio(), n))
            full.sort(reverse=True)

    print("### Отладка ### Сколько каждое слово набрало очков похожести")
    for score, i in full:
        print(i + str(score))

    return full[0]

arr = ['голубец', 'конь', 'голубцы', 'лист']
print("Итоговый результат:" + similar(arr)[1])

arr = ['стол', 'день', 'свет', 'клинок', 'светильник']
print("Итоговый результат:" + similar(arr)[1])

arr = ['восток', 'дань', 'исток', 'жир', 'голубь', 'да']
print("Итоговый результат:" + similar(arr)[1])

Результат работы:

### Отладка ### Сколько каждое слово набрало очков похожести
голубцы0.8571428571428571
голубец0.8571428571428571
лист0.18181818181818182
лист0.18181818181818182
конь0.18181818181818182
конь0.18181818181818182
голубцы0.18181818181818182
голубцы0.18181818181818182
голубец0.18181818181818182
голубец0.18181818181818182
лист0.0
конь0.0
Итоговый результат:голубцы 

### Отладка ### Сколько каждое слово набрало очков похожести
светильник0.5714285714285714
свет0.5714285714285714
стол0.5
свет0.5
стол0.42857142857142855
светильник0.42857142857142855
светильник0.375
светильник0.2857142857142857
день0.2857142857142857
свет0.25
день0.25
стол0.2
клинок0.2
клинок0.2
день0.2
клинок0.125
стол0.0
свет0.0
клинок0.0
день0.0
Итоговый результат:светильник

### Отладка ### Сколько каждое слово набрало очков похожести
исток0.7272727272727273
восток0.7272727272727273
дань0.6666666666666666
да0.6666666666666666
исток0.25
жир0.25
дань0.2
голубь0.2
исток0.18181818181818182
голубь0.18181818181818182
голубь0.16666666666666666
восток0.16666666666666666
исток0.0
исток0.0
жир0.0
жир0.0
жир0.0
жир0.0
дань0.0
дань0.0
дань0.0
да0.0
да0.0
да0.0
да0.0
голубь0.0
голубь0.0
восток0.0
восток0.0
восток0.0
Итоговый результат:исток

Answer 3

[raiboon]

https://en.wikipedia.org/wiki/Levenshtein_distance

Comments

[Александр]

def levenshtein(s, t):
        ''' From Wikipedia article; Iterative with two matrix rows. '''
        if s == t: return 0
        elif len(s) == 0: return len(t)
        elif len(t) == 0: return len(s)
        v0 = [None] * (len(t) + 1)
        v1 = [None] * (len(t) + 1)
        for i in range(len(v0)):
            v0[i] = i
        for i in range(len(s)):
            v1[0] = i + 1
            for j in range(len(t)):
                cost = 0 if s[i] == t[j] else 1
                v1[j + 1] = min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost)
            for j in range(len(v0)):
                v0[j] = v1[j]

        return v1[len(t)]

print(levenshtein('голубец', 'конь'))
print(levenshtein('голубец', 'голубцы'))

Answer 4

[Salavat Sharapov]

а = ['голубец', 'конь', 'голубцы', 'лист']
for b in a:
     if b == 'голубцы':
          print 'голубец'
      else:
           countinue

нет?

Comments

[pcdesign]

Нет, вы заранее не знаете какие там будут слова.
У вас есть список неких слов. Из которых надо найти максимально похожие.

[Salavat Sharapov]

Ну дык опишите это в условии *(.

[pcdesign]

Вопрос называется "Как найти похожие слова в списке?"

[Alexv01]

А что для вас "похожие", вот это и опишите

[pcdesign]

Alexv01: это видно из примеров, которые я привел

[Alexv01]

Кому видно?)
А вы программист?))) Дык опишите в условиии это.

[pcdesign]

Alexv01: С таким же успехом можно спросить, а что для вас "слово"?
Напишите в условии.

[Alexv01]

Ваше условие задачи, вам и описывать

Answer 5

[yttrium]

Помимо вычислений различных расстояний, можно пойти путем где на первом этапе нормализовать слова, на втором уже сравнивать нормальные формы. Нормализовать слова можно так называемым стеммером, например, из пакета nltk.

Comments

[Andrey Dugin]

Из пушки по воробьям