在一个字符串列表中找到最常见的子字符串？

Question

我有一个Python字符串列表，想从所有名称中删除一个共同的子字符串。

在阅读了类似的 答案 后，我使用 SequenceMatcher 差不多可以达到期望的结果。

但只有当所有项都有一个共同的子字符串时才能实现：

From List:
string 1 = myKey_apples
string 2 = myKey_appleses
string 3 = myKey_oranges

common substring = "myKey_"

To List:
string 1 = apples
string 2 = appleses
string 3 = oranges

然而，我有一个稍微有些杂乱的列表，其中包含一些不符合同一命名约定的分散项。

我想从大多数中删除“最常见”的子字符串：

From List:
string 1 = myKey_apples
string 2 = myKey_appleses
string 3 = myKey_oranges
string 4 = foo
string 5 = myKey_Banannas

common substring = ""

To List:
string 1 = apples
string 2 = appleses
string 3 = oranges
string 4 = foo
string 5 = Banannas

我需要一种方法来匹配“myKey_”子字符串，以便可以从所有名称中删除它。

但是，当我使用SequenceMatcher时，“foo”项目会导致“最长匹配”等于空白“”。

我认为解决这个问题的唯一方法是找到“最常见的子字符串”。但是如何实现呢？

---

基本示例代码：

from difflib import SequenceMatcher

names = ["myKey_apples",
"myKey_appleses",
"myKey_oranges",
#"foo",
"myKey_Banannas"]

string2 = names[0]
for i in range(1, len(names)):
    string1 = string2
    string2 = names[i]
    match = SequenceMatcher(None, string1, string2).find_longest_match(0, len(string1), 0, len(string2))

print(string1[match.a: match.a + match.size]) # -> myKey_

- Logic1

---

我认为你实际上并不想删除最常见的子字符串。它通常只有一个字母。例如，你所有的字符串都包含字母s（例如，apples以s结尾）。有两个感兴趣的数字：子字符串的长度和包含子字符串的搜索空间的百分比。当你增加其中一个时，另一个就会减少。 - Toothpick Anemone

我认为这会有所帮助：https://en.wikipedia.org/wiki/Longest_common_substring_problem - Jethro Cao

Answer 1

假设 names = ["myKey_apples", "myKey_appleses", "myKey_oranges", "foo", "myKey_Banannas"]

我能想到的一个 O(n^2) 解法是找出所有可能的子字符串，并将它们存储在一个带有出现次数的字典中:

substring_counts={}

for i in range(0, len(names)):
    for j in range(i+1,len(names)):
        string1 = names[i]
        string2 = names[j]
        match = SequenceMatcher(None, string1, string2).find_longest_match(0, len(string1), 0, len(string2))
        matching_substring=string1[match.a:match.a+match.size]
        if(matching_substring not in substring_counts):
            substring_counts[matching_substring]=1
        else:
            substring_counts[matching_substring]+=1

print(substring_counts) #{'myKey_': 5, 'myKey_apples': 1, 'o': 1, '': 3}

然后选择出现次数最多的子字符串

import operator
max_occurring_substring=max(substring_counts.iteritems(), key=operator.itemgetter(1))[0]
print(max_occurring_substring) #myKey_

- Sruthi

---

现在这才是天堂般的东西！甚至可以处理这个疯狂的列表：["sti_myKey_123","sti_myKey_233","stimm_myKey_676","sti_myKey_879","foo","sti_myKey_2345","sti_myKey_test3","ti_myKey_123"]，结果为"sti_myKey_"。非常感谢 :) - Logic1

其他人可能也想查看SequenceMatcher.get_matching_blocks https://www.kite.com/python/docs/difflib.SequenceMatcher.get_matching_blocks - Under-qualified NASA Intern

Answer 2

这是一个过于冗长的解决方案：

def find_matching_key(list_in, max_key_only = True):
  """
  returns the longest matching key in the list * with the highest frequency
  """
  keys = {}
  curr_key = ''

  # If n does not exceed max_n, don't bother adding
  max_n = 0

  for word in list(set(list_in)): #get unique values to speed up
    for i in range(len(word)):
      # Look up the whole word, then one less letter, sequentially
      curr_key = word[0:len(word)-i]
      # if not in, count occurance
      if curr_key not in keys.keys() and curr_key!='':
        n = 0
        for word2 in list_in:
          if curr_key in word2:
            n+=1
        # if large n, Add to dictionary
        if n > max_n:
          max_n = n
          keys[curr_key] = n
    # Finish the word
  # Finish for loop  
  if max_key_only:
    return max(keys, key=keys.get)
  else:
    return keys    

# Create your "from list"
From_List = [
             "myKey_apples",
             "myKey_appleses",
             "myKey_oranges",
             "foo",
             "myKey_Banannas"
]

# Use the function
key = find_matching_key(From_List, True)

# Iterate over your list, replacing values
new_From_List = [x.replace(key,'') for x in From_List]

print(new_From_List)
['apples', 'appleses', 'oranges', 'foo', 'Banannas']

< p > < em > 不用说，如果使用递归的话，这个解决方案看起来会更整洁。不过，我为你勾画了一个粗略的动态规划解决方案。

- Yaakov Bressler

Answer 3

我会首先找到出现最多次数的起始字母。然后，我会取出每个以该起始字母开头的单词，并检查这些单词是否有匹配的字母。最后，我会从每个起始单词中删除已找到的前缀。

from collections import Counter
from itertools import takewhile

strings = ["myKey_apples", "myKey_appleses", "myKey_oranges", "berries"]

def remove_mc_prefix(words):
    cnt = Counter()
    for word in words:
        cnt[word[0]] += 1
    first_letter = list(cnt)[0]

    filter_list = [word for word in words if word[0] == first_letter]
    filter_list.sort(key = lambda s: len(s)) # To avoid iob

    prefix = ""
    length = len(filter_list[0])
    for i in range(length):
        test = filter_list[0][i]
        if all([word[i] == test for word in filter_list]):
            prefix += test
        else: break
    return [word[len(prefix):] if word.startswith(prefix) else word for word in words]

print(remove_mc_prefix(strings))

输出：['苹果', 'appleses'， '橙子'， '浆果']

- RoyM

Answer 4

从Python字符串列表中查找最常见的子字符串

我已经在 python-3.10.5 上进行了测试，希望对你有用。 我有相同的用例，但是任务类型不同，我只需要从100多个文件中找到一个 common-pattern-string 作为 regular-expression 使用。

你的基本示例代码在我的情况下不起作用。因为第一个检查第二个，第二个检查第三个，第三个检查第四个，依此类推。所以，我将其更改为最常见的子字符串，并将逐个进行检查。

这段代码的缺点是，如果某些内容与最常见的子字符串不相同，则最终的最常见子字符串将为空。 但在我的情况下，它是有效的。

from difflib import SequenceMatcher
for i in range(1, len(names)):
    if i==1:
        string1, string2 = names[0], names[i]
    else:
        string1, string2 = most_common_substring, names[i]
    match = SequenceMatcher(None, string1, string2).find_longest_match(0, len(string1), 0, len(string2))
    most_common_substring = string1[match.a: match.a + match.size]

print(f"most_common_substring : {most_common_substring}")

Python Python 3Python Difflib

- P_M