DjangoBB LoFi version

Найти - Пользователи

Полная версия: удаление "похожих" строк

Начало » Python для новичков » удаление "похожих" строк

qwerthon

Фев. 6, 2011 02:05:13

к примеру есть строки

новы сапоги
новые сапоги
новы и сапоги

или

текст
текст
новые сапоги
текст
текст
новые сапоги
текст
текст
текст
сапоги новые
текст
текст
текст

как силами питона фильтрануть текст и найти максимально похожие куски
- желательно чтоб распознавалась перестановка слов ( в приделах предложения )
- различие строк вплоть до 1 символа ( так называемые опечатки )

где-то мельком видел библиотеку для сравнения файлов ( на базе хеш-функций или что-то подобное …) - возможно она подойдет для данной задачи?

подскажите как такое реализовать.
спасибо.

igor.kaist

Фев. 6, 2011 08:50:05

qwerthon
где-то мельком видел библиотеку для сравнения файлов ( на базе хеш-функций или что-то подобное …)

Нет, это не подойдет.
Сейчас проснется Zubchik и напишем вам алгоритм :))

Андрей Светлов

Фев. 6, 2011 09:25:21

Сначала определитесь: что такое “максимально похожий кусок”?

truporez

Фев. 6, 2011 11:11:18

начните копать отсюда http://pypi.python.org/pypi/python-Levenshtein/

ptax

Фев. 6, 2011 12:48:22

У меня была подобная задача. Я искал регулярным выражением.
Если есть более адекватное решения с удовольствием бы посмотрел.

Zubchick

Фев. 6, 2011 12:50:24

Если текст небольшой, то можно накапливать каждую строку в хеш-таблицу, если она не похожа ни на одну строку из хеш-таблицы, а если похожа, то накапливать индекс с троки.

from collections import defaultdict
table = defaultdict(list)
a = ['ololo', 'hahaha', 'ololo', 'bugaga', 'ololo']

def similar(word1, word2):
    if word1 == word2:
        return 100
    else:
        return 0

for i, word in enumerate(a):
    for j in table:
        if similar(word, j) > 90:
            table[j].append(i)
            break
    else:
        table[word].append(i)

>>> table
>>> defaultdict(<type 'list'>, {'ololo': [0, 2, 4], 'bugaga': [3], 'hahaha': [1]})

вместо функции similar придется, конечно написать свою какую-то, Например на основе расстояния Левенштейна, который выше указали, ну или еще какой алгоритм из этих:
Hamming Distance
Levenstein Distance (Edit Distance)
Damerau-Levenstein Distance
Longest common substring
Longest common subsequence
Needleman-Wunsch distance
Smith–Waterman distance

qwerthon

Фев. 6, 2011 16:56:46

всем спасибо, расстояния Левенштейна ( и подобные ) должно помочь

я и не думал что их “реализация” есть на питоне …. чем дальше, тем больше мне этот язык нравится -)