如何按子串模式对列表进行排序

Question

我试图根据类似的子字符串对值列表进行排序。我想把它分组在一个dict of list中，一个键是类似的子字符串，值是这些分组值的列表。你知道吗

例如（实际列表有24k个条目）：

test_list = [ 'Doghouse Amsterdam', 'Doghouse Antwerp', 'Doghouse Vienna', 
        'House by KatSkill', 'Garden by KatSkill', 'Meadow by KatSkill']

收件人：

resultdict = { 
'Doghouse' : ['Doghouse Amsterdam', 'Doghouse Antwerp', 'Doghouse Vienna'],
'by KatSkill' : [ 'House by KatSkill', 'Garden by KatSkill', 'Meadow by KatSkill' ]
}

我试过以下方法，但一点用都没有。你知道吗

from itertools import groupby 
test_list = [ 'Doghouse Amsterdam', 'Doghouse Antwerp', 'Doghouse Vienna', 
            'House by KatSkill', 'Garden by KatSkill', 'Meadow by KatSkill']


res = [list(i) for j, i in groupby(test_list, 
                          lambda a: a.partition('_')[0])]

Answer 1

下面是一个可能更简单/更快的实现

from collections import Counter
from itertools import groupby
import pprint

# Strategy:
# 1.  Find common words in strings in list
# 2.  Group strings which have the same common words together

def find_commond_words(lst):
  " finds strings with commond words "
  cnt = Counter()
  for s in lst:
    cnt.update(s.split(" "))

  # return words which appear in more than one string
  words = set([k for k, v in cnt.items() if v > 1])
  return words

def groupping_key(s, words):
  " Key function for groupping strings with common words in the same sequence"
  k = []
  for i in s.split():
    if i in words:
      k.append(i)
  return ' '.join(k)

def calc_groupings(lst):
  " Generate the string groups based upon common words "
  common_words = find_commond_words(lst)

  # Group strings with common words
  g = groupby(lst, lambda x: groupping_key(x, common_words))

  # Result
  return {k: list(v) for k, v in g}

t = ['Doghouse Amsterdam', 'Doghouse Antwerp', 'Doghouse Vienna', 
        'House by KatSkill', 'Garden by KatSkill', 'Meadow by KatSkill']

pp = pprint.PrettyPrinter(indent=4)
pp.pprint(calc_groupings(t))

输出

{   'Doghouse': ['Doghouse Amsterdam', 'Doghouse Antwerp', 'Doghouse Vienna'],
'by KatSkill': [   'House by KatSkill',
                   'Garden by KatSkill',
                   'Meadow by KatSkill']}

Answer 2

首先，查找在输入列表的另一个字符串中出现的所有以“”分隔的子字符串。在此过程中，构建一个字典，其中包含所有相应的子字符串作为键，输入字符串作为值。这将返回一个只包含单个子字符串作为键的字典。使用该示例返回：

{'by': ['Garden by KatSkill', 'Meadow by KatSkill', 'House by KatSkill'], 'KatSkill': ['Garden by KatSkill', 'Meadow by KatSkill', 'House by KatSkill'], 'Doghouse': ['Doghouse Antwerp', 'Doghouse Vienna', 'Doghouse Amsterdam']}

为了获得预期的结果，需要压实。对于压缩，利用每个字典键也是字典字符串列表的一部分这一事实是有益的。因此，遍历字典值并再次将字符串拆分为子字符串。然后按子字符串列表的顺序遍历子字符串，并确定包含字典键的子字符串列表范围。将相应的范围添加到新的dict中。对于24k个条目，这可能需要一段时间。请参见下面的源代码：

mylist = [ 'Doghouse Amsterdam', 'Doghouse Antwerp', 'Doghouse Vienna', 
        'House by KatSkill', 'Garden by KatSkill', 'Meadow by KatSkill']

def findSimilarSubstrings(list):
    res_dict = {}
    for string in list:
        substrings = string.split(" ")
        for otherstring in list:
            # Prevent check with the same string
            if otherstring == string:
                continue
            for substring in substrings:
                if substring in otherstring:
                   if not(substring in res_dict):
                       res_dict[substring] = []
                   # Prevent duplicates
                   if not(otherstring in res_dict[substring]):
                       res_dict[substring].append(otherstring)
    return res_dict

def findOverlappingLists(dict):
    res_dict = {}
    for list in dict.values():
        for string in list:
            substrings = string.split(" ")
            lastIndex = 0
            lastKeyInDict = False
            substring = ""
            numsubstrings = len(substrings)
            for i in range(len(substrings)):
               substring = substrings[i]
               if substring in dict:
                    if not(lastKeyInDict):
                        lastIndex = i
                        lastKeyInDict = True
               elif lastKeyInDict:
                   commonstring = " ".join(substrings[lastIndex:i])
                   # Add key string to res_dict
                   if not(commonstring in res_dict):
                      res_dict[commonstring] = []
                   # Prevent duplicates
                   if not(string in res_dict[commonstring]):
                      res_dict[commonstring].append(string)
                   lastKeyInDict = False
            # Handle last substring
            if lastKeyInDict:
                commonstring = " ".join(substrings[lastIndex:numsubstrings])
                if not(commonstring in res_dict):
                    res_dict[commonstring] = []
                if not(string in res_dict[commonstring]):
                    res_dict[commonstring].append(string)
    return res_dict

# Initially find all the substrings (seperated by " ") returning:
# {'by': ['Garden by KatSkill', 'Meadow by KatSkill', 'House by KatSkill'],
#  'KatSkill': ['Garden by KatSkill', 'Meadow by KatSkill', 'House by KatSkill'],
#  'Doghouse': ['Doghouse Antwerp', 'Doghouse Vienna', 'Doghouse Amsterdam']}
similiarStrings = findSimilarSubstrings(mylist)
# Perform a compaction on similiarStrings.values() by lookup in the dictionary's key set
resultdict = findOverlappingLists(similiarStrings)

Answer 3

mylist = [ 'Doghouse Amsterdam', 'Doghouse Antwerp', 'Doghouse Vienna', 
            'House by KatSkill', 'Garden by KatSkill', 'Meadow by KatSkill']
test = ['Doghouse', 'by KatSkill']

使用听写和列表理解：

res = { i: [j for j in mylist if i in j] for i in test}

或者设置你的dict，并使用列表理解循环

resultdict = {}
for i in test:
     resultdict[i] = [j for j in mylist if i in j]