Как найти похожие строки

[ReNzRv]

Из потока строк нужно найти "похожие" строки группами, или похожие на одну указанную.

Похожие - это строки отличающиеся не более чем на N любых символов в любом месте и последовательности. Соответственно должно указыватся только число N символов.

[Azure]

из потока строк найти похожие?

Уточните: надо вывести все похожие строки группами или найти похожую на 1 заданную?
Вряд ли задача решается регулярками — надо ведь считать количество совпадений и сравнивать с N (решается с помощью awk и других высокоуровневых языках на раз-два)

[ReNzRv]

Azure,
Группами, но и поиск похожей на одну указанную тоже очень пригодится)

[Azure]

Код: (python) [Выделить]

#!/usr/bin/python3

import sys

def diff_weight(pattern, line, weight):
    source = list(line)
    count = 0
    for s in pattern:
        try:
            source.remove(s)
        except ValueError:
            count += 1
            if count > weight:
                return False
    if len(source) + count > weight:
        return False
    return True

weight = int(sys.argv[1])
try:
    with open(sys.argv[2]) as file:
        lines = file.readlines()
except IndexError:
    lines = sys.stdin.readlines()

while lines:
    pattern = lines.pop()
    print(pattern, end="")
    for i in range(len(lines)-1, -1, -1):
        if diff_weight(pattern, lines[i], weight):
            print(lines[i], end="")
            lines.pop(i)

[Azure]

Вот как важно иметь тестовые данные… Элементарные ошибки сам бы поправил.
Ещё попытка!

[ReNzRv]

Код: [Выделить]

./Find_similar_strings.py 5 "test_text.txt">>>

Код: [Выделить]

*куски текста*
Traceback (most recent call last):
  File "./Find_similar_strings.py", line 30, in <module>
    if diff_weight(pattern, lines[i], weight):
IndexError: list index out of range
test_text.txt прикрепил.
Пользователь добавил сообщение 20 Июля 2016, 21:00:53:скрипт должен вывести например эти строки:

(Нажмите, чтобы показать/скрыть)

"W-F1" - переключиться на рабочее место 1;
"W-F2" - переключиться на рабочее место 2;
"W-F3" - переключиться на рабочее место 3;
"W-F4" - переключиться на рабочее место 4;

сортировать строки нужно? или он найдет похожие независимо от расположения в файле/потоке?

[Azure]

Строка «Код:» и пустые — подобные.
Выводить надо только имеющие подобных? Я просто сделал групировку…

[ReNzRv]

Да, все подобные строки группами кроме пустых. Главное чтобы выполнялось условие: "похожие - это строки отличающиеся не более чем на N любых любых символов в любом месте и последовательности"

[Azure]

В Вашем файле при №=5 получается 3 группы

Код: (html5) [Выделить]













Код:

=====================================================
"A-F2" - показать диалоговое окно панели "Выполнить программу";
"W-r" - показать диалоговое окно панели "Выполнить программу";
=====================================================
"W-F4" - переключиться на рабочее место 4;
"W-F3" - переключиться на рабочее место 3;
"W-F2" - переключиться на рабочее место 2;
"W-F1" - переключиться на рабочее место 1;

[ReNzRv]

Почему "Код:" попал в группу? ("код" в файле 1 шт.)

Строки тогда будут фильтроватся через: | sed '/^\s*$/d'

[Azure]

Пропускает пустые строки и выводит только подобные

Код: (python) [Выделить]

#!/usr/bin/python3

import sys

def diff_weight(pattern, line, weight):
    source = list(line)
    if len(pattern) > len(line):
        count = 0
    else:
        count = len(line) - len(pattern)
    for s in pattern:
        try:
            source.remove(s)
        except ValueError:
            count += 1
            if count > weight:
                return False
    return True
 
groups=[]
weight = int(sys.argv[1])
try:
    with open(sys.argv[2]) as file:
        lines = file.readlines()
except IndexError:
    lines = sys.stdin.readlines()
 
lines = list(filter("\n".__ne__, lines))
while lines:
    pattern = lines.pop()
    group = pattern
    for i in range(len(lines)-1, -1, -1):
        if diff_weight(pattern, lines[i], weight):
            group += lines[i]
            lines.pop(i)
    if group != pattern:
        groups.append(group)
print(*groups, sep="========\n", end="")Пользователь добавил сообщение 20 Июля 2016, 21:54:18:

Почему "Код:" попал в группу? ("код" в файле 1 шт.)

«Код:» в группе с пустыми строками т.к. == 4 символа, т.е. отличается от пустого на 4 что <5

[ReNzRv]

Понял, а разделение групп пустой строчкой или "======" можно?
Строки группы:

Код: [Выделить]

"W-F4" - переключиться на рабочее место 4;
"W-F3" - переключиться на рабочее место 3;
"W-F2" - переключиться на рабочее место 2;
"W-F1" - переключиться на рабочее место 1;отличаются друг от друга на 2 символа, но при значении N 3 или 2 вывода нет.
?
Пользователь добавил сообщение 20 Июля 2016, 23:02:54:Спасибо, уже почти хорошо)
Скопировал 1 строчку в файле, добавил 1 символ, но при н=1 вывода этих строк не получил.
Не принципиально, но добавить бы еще разделитель в начало и конец.

[Azure]

Сделал вроде как.

[ReNzRv]

Теперь похоже все верно, спасибо вам, позже буду еще тестить на других примерах строк,
если найду какой баг -напишу.
А вариант для поиска похожих на одну указанную строку будет?

Пользователь добавил сообщение 20 Июля 2016, 23:53:12:Выводятся дубликаты строк, т.е от н=0 - что не нужно, хотя можно исправить юником.
Тут подумал, может полезнее/лучше будет добавить аргумент N (min)?

[Azure]

Добавил пару проверок

Код: (python) [Выделить]

#!/usr/bin/python3

import sys

def diff_weight(pattern, line, weight):
    source = list(line)
    if len(pattern) >= len(line):
        count = 0
    else:
        count = len(line) - len(pattern)
    for s in pattern:
        try:
            source.remove(s)
        except ValueError:
            count += 1
            if count > weight:
                return False
    return True
 
groups=[]

try:
    weight = int(sys.argv[1])
except (IndexError, ValueError):
    print("ERROR: The decimal next to script.name should indicate max difference")
    exit(1)

try:
    with open(sys.argv[2]) as file:
        lines = file.readlines()
except IndexError:
    lines = sys.stdin.readlines()
lines = list(filter("\n".__ne__, lines))
if not lines:
    print("ERROR: There are no input lines")
    exit(2)

while lines:
    pattern = lines.pop()
    group = pattern
    for i in range(len(lines)-1, -1, -1):
        if diff_weight(pattern, lines[i], weight):
            group += lines.pop(i)
    if group != pattern:
        groups.append(group)
print(*groups, sep="========\n", end="")

А вариант для поиска похожих на одну указанную строку будет?

Так он же и есть в виде функции diff_weight, только надо цикл убрать чтоб не все строки проверял, а только 1.

Выводятся дубликаты строк, т.е от н=0 - что не нужно, хотя можно исправить юником.
Тут подумал, может полезнее/лучше будет добавить аргумент N (min)?

Совершенству конца нет. Тестируйте пока.