Как реализовать поиск вхождений разной длины в строку с большего к меньшей?

Question

[Bruceee]

Подскажите, пожалуйста, каким образом можно реализовать следующее:
есть три пары значений ("a b c"; "x") , ("a b"; "y"), ("a", "z") в виде словаря dict.

Во входной строке необходимо искать и заменять подстроки из словаря в такой логике:

• если в строке есть подстрока "a b c", то надо заменить вхождение "a, b, c" на "x", согласно первой паре
  
• если в строке есть подстрока "a b", то надо заменить вхождение "a, b" на "y", согласно второй паре
  
• если в строке есть только "a", тогда надо заменить на "z", согласно третьей паре
  

То есть если есть длинные последовательности, имеющие вхождение в строку, то сначала заменить их, и так далее до самых коротких.

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

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

Подскажите, пожалуйста, какую структуру данных и как лучше использовать?
Как хранить новую структуру данных? Словарь легко хранить как текст в отдельном файле, можно ли так поступить с созданной структурой данных?

Answer 1

[longclaps]

import re

d = {"a b c": "x", "a b": "y", "a": "z"}
data = "a b c a b a a a b c"
print(re.sub(r'a( b( c)?)?', lambda m: d[m.group()], data))
print(re.sub(r'a b c|a b|a', lambda m: d[m.group()], data)) # можно и так

Comments

[Bruceee]

longclaps: Спасибо, а можно разъяснить более подробно каждую строчку?

[longclaps]

Bruceee: Сдаётся мне, если тебе надо две первые строчки объяснять, дело это тухлое.

[Bruceee]

longclaps: Конечно же, я про последние две)

[longclaps]

Bruceee: Про регулярные выражения я вкратце рассказывать не буду, тема обширная, широко освещенная и заслуживающая внимания. Гугли.
Вместо лямбды могла стоять самая обычная функция

def f(m): # объявляю
    return d[m.group()]
# использую
print(re.sub(r'a b c|a b|a', f, data))

Лучше сделаю замечание к задаче. Выглядит как попытка сжать, заархивировать строку. Рассмотрим такой кейс:

d = {"abc": "x", "def": "y", "bcde": "z"}
data = "abcdef"
# возможна запаковка начиная с длиннейшей подстановки
 "abcdef" -> "aze"
# а можно и короче
 "abcdef" -"xy"

Задача оптимальной упаковки не так тривиальна, я бы посоветовал почитать что-нибудь, на www.compression.ru была книжка.

Answer 2

[Bruceee]

Как у меня получилось решить свой вопрос:
создаем упорядоченный список из кортежей,
где каждый кортеж будет состоять из:
числа - количество слов в ключе
строки - ключ, который мы ищем в сообщении пользователя
строки - значение, на которое мы меняем ключ

Далее парсим словарь в созданную структуру, затем сортируем:

values_list_sorted = sorted(values_list, key=lambda x: x[0], reverse=True)

Конечно, вариант, предложенный longclaps намного более изящный :)

Answer 3

[Александр]

В модуле collections есть структура OrderedDict, которая является словарём, хранящим порядок элементов.
Если заполнить его парами ключ-значение в порядке убывания длины ключа, то именно так их он и сохранит, и при итерации будет отдавать сначала длинные ключи.
Единственное, что нужно помнить - после того, как такой словарь построен, при необходимости добавить новую пару, словарь нужно будет целиком заново перестраивать.

Answer 4

[maxfox]

Вам нужно хранить правила замен не в словаре, а, например, в списке кортежей. Словарь не имеет смысла в данной задаче, т.к. вы будете перебирать все варианты замен, а не выбирать их по ключу. В итоге проходим по списку кортежей и делаем замену через .replace(). Две строчки кода.

Answer 5

[xmoonlight]

1. Упорядочить словарь по кол-ву слов: самые длинные цепочки - вверх.
2. Производить замену в обычном режиме: строку за строкой с проверкой текущей строки на все возможные совпадения по количеству слов и т.д.

Comments

[Bruceee]

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

[xmoonlight]

Bruceee: тогда уж правильнее - по кол-ву слов в заменяемой строке.

[longclaps]

Bruceee:
словарь является неупорядоченной структурой данных
сортирую кортежи в словаре
У тебя не побалуешь - ты отсортируешь кого угодно, даже словарь )

[Bruceee]

longclaps: Описка, сортирую кортежи в списке :)