在一个字符串列表中查找最小的唯一n-gram列表

Question

我有一个包含50,000个字符串（城市名称）的清单，需要找到最小的字符三元组（最好是n-gram），使得每个字符串都至少被一个三元组命中。考虑以下列表: ['amsterdam', 'rotterdam', 'haarlem', 'utrecht', 'groningen']

识别三元组的列表长度为4，并且应该是以下内容（也可能有其他选择）：

['ter', 'haa', 'utr', 'gro']

我认为我的解决方案找到了正确答案，但是在使用其他列表时它给出了错误的答案。

from collections import Counter

def identifying_grams(list, n=3):

    def f7(seq):
        seen = set()
        seen_add = seen.add
        return [x for x in seq if not (x in seen or seen_add(x))]

    def ngrams(text, n=3):
        return [text[i:i + n] for i in range(len(text) - n + 1)]

    hits = []
    trigrams = []
    for item in list:
      #  trigrams += ngrams(item)
        trigrams += f7(ngrams(item))

    counts = Counter(trigrams).most_common()

    for trigram, count in counts:
        items = []
        for item in list:
            if trigram in item:
                hits.append(trigram)
                items.append(item)
        for i in items:
            list.remove(i)

    return(f7(hits))

list1 = ['amsterdam','rotterdam','haarlem','utrecht','groningen']
print(identifying_grams(list1))
# Good, we get: ['ter', 'haa', 'utr', 'gro']

list2 = ['amsterdam','schiedam']
print(identifying_grams(list2))
# Good, we get: ['dam']

list3 = ['amsterdam','schiedam','terwolde','wolstad']
print(identifying_grams(list3))
# Ouch, we get: ['ter', 'dam', 'wol']
# this should be ['dam', 'wol'] as this is only 2 trigrams that identify the list...

到目前为止我已经得到两个答案，但是它们两个都有缺陷。Rupesh提供的一个对于小于10项的列表是不错的。我的列表有超过50000项。mujjiga的解决方案虽然不是完美的，但也能解决问题。

求Python大神提供一个完美而且可扩展的解决方案，如果运行效果良好并且每次运行都提供相同的解决方案，额外奖励！

- Jorden van Foreest

---

I need a the smallest list of character tri-grams (prefarably n-grams) so that every string is at least once hit by every tri-gram how is 'ter' a solution if it is not there in haarlem - mujjiga

"haa" 匹配 "haarlem"，"ter" 匹配 "rotterdam" 和 "amsterdam"。 - Jorden van Foreest

我需要最小可能的三元组列表，以至少一次命中城市列表中的每个项目。 - Jorden van Foreest

我建议您更改措辞，从“以便每个字符串至少被每个三元组命中一次”改为“以便每个字符串至少被一个三元组命中一次”。 - Rocky Li

好的观点。改变了问题。 - Jorden van Foreest

我运行您的代码并输入identifying_grams(list3)，输出结果为['dam', 'wol']。 - גלעד ברקן

Answer 1

以下是@mujjiga答案的理论分析：

您可以创建共享相同ngram的单词类。您想选择覆盖整个单词集的最小类数（即最小的ngram数）。这是集合覆盖问题。不幸的是，此问题是NP难问题（而不是NP完全问题，感谢@mujjiga）。(编辑：因此，没有已知的解决方案可以在合理的时间内给出预期结果。)贪心算法几乎是最佳解决方案（请参见https://cs.stackexchange.com/questions/49777/is-greedy-algorithm-the-best-algorithm-for-set-cover-problem）。

请注意，即使贪心算法可能会产生奇怪的结果。取集合{a，b}，{b，c}，{c，d}和超集{a，b，c，d}为例。三个子集都是最大的。如果您首先取{b，c}，则需要另外两个子集来覆盖超集。如果您取{a，b}或{c，d}，则只需要两个子集。

让我们使用贪心算法，并考虑实现。创建将ngram映射到单词的字典的代码非常简单：

all_words= ['amsterdam','schiedam','werkendam','amstelveen','schiebroek','werkstad','den haag','rotjeknor','gouda']
n=3
words_by_ngram = {}
for word in all_words:
    for ngram in (word[i:i+n] for i in range(0, len(word)-n+1)):
        words_by_ngram.setdefault(ngram, set()).add(word)

setdefault与get等效，如果键ngram存在，则创建一个空集合。这是O(|all_words|*|len max word|)的复杂度。

现在，我们想要获取单词最多的ngram，并从字典中删除这些单词。重复此操作，直到获得所需的单词。

以下是简单版本：

s = set(all_words) # the target
gs = set()
d = words_by_ngram.copy() # for the display
while s:
    # take the the best ngram
    ngram, words = max(d.items(), key=lambda i: len(i[1])) # sort on word count
    # remove the words from the dictionary and delete the ngrams whose words have been already found
    d = {k:v for k, v in ((k, v - words) for k, v in d.items()) if len(v)}
    gs.add(ngram) # add the ngram to the result
    s -= words # remove the words from the target

# check
assert set().union(*[words_by_ngram[g] for g in gs]) == set(all_words)
# display
for g in gs:
    print("{} -> {}".format(g, words_by_ngram[g]))

输出：

ams -> {'amstelveen', 'amsterdam'}
gou -> {'gouda'}
wer -> {'werkstad', 'werkendam'}
rot -> {'rotjeknor'}
dam -> {'amsterdam', 'werkendam', 'schiedam'}
sch -> {'schiebroek', 'schiedam'}
den -> {'den haag'}

这第二步的复杂度为O(|all_words|*|ngrams|)，因为需要循环查找最大值并更新字典。因此，总体复杂度为O(|all_words|*|ngrams|)。

可以通过使用优先队列来降低复杂度。检索最佳ngram的成本为O(1)，但将映射到ngram的单词的长度更新具有O(lg |ngrams|)的优先级。

import heapq
class PriorityQueue:
    """Adapted from https://docs.python.org/3/library/heapq.html#priority-queue-implementation-notes
    A prority of 1 invalidates the entries
    """
    def __init__(self, words_by_ngram):
        self._d = {ngram:[-len(words), (ngram, words)] for ngram, words in words_by_ngram.items()}
        self._pq = list(self._d.values())
        heapq.heapify(self._pq)

    def pop(self):
        """get the ngram, words tuple with the max word count"""
        minus_len, (ngram, words) = heapq.heappop(self._pq)
        while minus_len == 1: # entry is not valid
            minus_len, (ngram, words) = heapq.heappop(self._pq)
        return ngram, words

    def update(self, ngram, words_to_remove):
        """remove the words from the sets and update priorities"""
        del self._d[ngram]
        ngrams_to_inspect = set(word[i:i+n] for i in range(0, len(word)-n+1)
                        for word in words_to_remove)
        for ngram in ngrams_to_inspect:
            if ngram not in self._d: continue
            self._d[ngram][0] = 1 # use the reference to invalidate the entry
            [L, (ngram, words)] = self._d[ngram]
            words -= words_to_remove
            if words:
                self._d[ngram] = [-len(words), (ngram, words)] # new entry
                heapq.heappush(self._pq, self._d[ngram]) # add to the pq (O(lg ngrams))
            else: # nothing left: remove it from dict
                del self._d[ngram]


pq = PriorityQueue(words_by_ngram)
gs = set()
s = set(all_words) # the target
while s:
    # take the the best ngram
    ngram, words = pq.pop()
    gs.add(ngram) # add the ngram to the result
    s -= words # remove the words from the target
    # remove the words from the dictionary and update priorities
    pq.update(ngram, words)

使用这段代码，总体优先级降至O(|all_words|*|lg ngrams|)。话虽如此，我很想知道这是否比之前的版本更快，其中包含50k个项目。

- jferard

---

糟糕，我希望你已经解决了这个问题，并让我离解决P = NP和100万美元更近了一步。参见en.wikipedia.org/wiki/Millennium_Prize_Problems。 - Jorden van Foreest

@JordenvanForeest 抱歉！我已经解决了这个问题并拿到了100万美元：P = NP <=> P=0或N=1。 - jferard

集合覆盖问题的决策版本是NP完全问题，而集合覆盖的优化/搜索版本是NP难问题。因此，寻找最小集合覆盖应该是NP难问题，而不是NP完全问题。 - mujjiga

Answer 2

下面是贪心算法的一个实现示例，用于集合覆盖。在我的机器上，它在50,000个英语词汇上运行约半秒钟。输出结果并不总是最优的，但在实践中通常很接近最优解。您可以使用整数规划的外部库将实例求解到最优解，但我不知道您是否想朝这个方向发展。

以下代码动态维护了ngrams和未覆盖文本的二分图。其中一个微妙之处在于，由于Python标准库中缺乏内置堆，因此我利用了键只增加一点的事实来伪造一个堆。每个ngram都带有小于或等于其应该具有的得分的堆，并且当我们取出最小值时，如果它小于它应该是的值，我们就会将其放回并更新值。否则，我们知道它就是真正的最小值。

此代码应该产生确定性输出。在每个步骤中，它选择按字典顺序最小的ngram，以覆盖最大数量的未覆盖文本。

import collections
import heapq


def ngrams_from_text(text, n):
    return {text[i:i + n] for i in range(len(text) - n + 1)}


def greedy_ngram_cover(texts, n):
    neighbors_of_text = {text: ngrams_from_text(text, n) for text in texts}
    neighbors_of_ngram = collections.defaultdict(set)
    for text, ngrams in neighbors_of_text.items():
        for ngram in ngrams:
            neighbors_of_ngram[ngram].add(text)
    heap = [(-len(neighbors), ngram)
            for (ngram, neighbors) in neighbors_of_ngram.items()]
    heapq.heapify(heap)
    cover = []
    while neighbors_of_text:
        score, ngram = heapq.heappop(heap)
        neighbors = neighbors_of_ngram[ngram]
        if score != -len(neighbors):
            heapq.heappush(heap, (-len(neighbors), ngram))
            continue
        cover.append(ngram)
        for neighbor in list(neighbors):
            for neighbor_of_neighbor in neighbors_of_text[neighbor]:
                neighbors_of_ngram[neighbor_of_neighbor].remove(neighbor)
            del neighbors_of_text[neighbor]
    return cover


print(
    greedy_ngram_cover(
        ['amsterdam', 'rotterdam', 'haarlem', 'utrecht', 'groningen'], 3))

- David Eisenstat

---

在我看来，选择集合覆盖方法是最好的。它具有双重优势，既能解决问题（这只是 DS 问题的某种重新表述），又是一个非常经典的问题，已经存在许多算法和实现。 - m.raynal

Answer 3

上面的解决方案失败了，原因如下：

• Counter 返回的三连字并不是按顺序排列的，所以如果你多次运行解决方案，你将随机获得所需的解决方案
• 而且你一旦找到组合就会立即返回，既不按长度顺序进行遍历，也没有找到满足问题的所有组合中最佳的组合

在这里，我按包含三连字符列表元素最少到最多的顺序进行遍历，然后在找到解决方案后立即返回。

from itertools import permutations

def checkTrigramsPresentInList(trigrams_list,input_list):
    for input_string in input_list:
        flag = False
        for trigram in trigrams_list:
            if trigram in input_string:
                flag = True
        if not flag:
            return False
    return True

def ngrams(text, n=3):
        return [text[i:i + n] for i in range(len(text) - n + 1)]

def identifying_grams(input_list, n=3):
    trigrams = []
    for item in input_list:
        trigrams += ngrams(item)
    len_of_trigrams = len(trigrams)
    trigrams_unique = list(set(trigrams))
    idx =1
    correct_tri_lists = []
    unique_trigrams_list = []
    while idx <= len_of_trigrams:
        trigrams_lists = permutations(trigrams_unique,idx)

        for trigrams_list in trigrams_lists:
            print(trigrams_list)
            if not trigrams_list in unique_trigrams_list:
                if checkTrigramsPresentInList(list(trigrams_list),input_list):
                    correct_tri_lists.append(list(trigrams_list))
            ##Uncomment below lines if only one combination is needed
                if correct_tri_lists:
                    return correct_tri_lists
                    unique_trigrams_list.append(trigrams_list)
        idx = idx+1


list1 = ['amsterdam','rotterdam','haarlem','utrecht','groningen']
print(identifying_grams(list1))
# # Good, we get: ['ter', 'haa', 'utr', 'gro']

list2 = ['amsterdam','schiedam']
print(identifying_grams(list2))
# # Good, we get: ['dam']

list3 = ['amsterdam','schiedam','terwolde','wolstad']
print(identifying_grams(list3))

- Rupesh Goud

---

注释掉的部分似乎不起作用……但不是必需的。它似乎给出了正确的输出，但每次都不同…… - Jorden van Foreest

如果我创建一个包含10个项目的列表，例如：['amsterdam'，'schiedam'，'werkendam'，'amstelveen'，'schiebroek'，'werkstad'，'den haag'，'rotjeknor'，'gouda']，我会遇到内存错误。 - Jorden van Foreest

是的，这可能会发生，因为我们在这里采用了完全的暴力方法。我们可以通过创建生成器而不是list(permutations(trigrams,idx))来避免内存错误，并对其进行遍历。但我不能保证执行速度。因为会有很多三元组的组合。随着元素数量的增加，速度会降低。 - Rupesh Goud

Answer 4

from nltk.util import ngrams

def load_dictonary(cities, n=3):
    ngram2cities = {}
    for city in cities:
        grams = [''.join(x) for x in ngrams(city,n)]
        for g in grams:
            if g in ngram2cities and city not in ngram2cities[g]:
                ngram2cities[g].append(city)
            else:
                ngram2cities[g] = [city]                
    return ngram2cities

def get_max(the_dict):
    n = 0
    the_max_key = None
    for key in the_dict :
        size = len(the_dict[key])
        if size > n:
            n = size
            the_max_key = key
    return the_max_key

def get_min_ngrams(cities, n=3):
    selected_ngrams = list()
    ngram2cities = load_dictonary(cities, n)
    ngram = get_max(ngram2cities)
    while ngram is not None:
        cities_covered = ngram2cities[ngram]
        ngram2cities.pop(ngram)
        selected_ngrams.append(ngram)        
        for city in cities_covered:
            for n in ngram2cities:
                if city in ngram2cities[n]:
                    ngram2cities[n].remove(city)
        ngram = get_max(ngram2cities)
    return selected_ngrams

cities_1 = ['amsterdam','rotterdam','haarlem','utrecht','groningen']
cities_2 = ['amsterdam','schiedam','terwolde','wolstad']
cities_3 = ['amsterdam','schiedam']
cities_4 = ['amsterdam','walwalwalwaldam']

print (get_min_ngrams(cities_1))
print (get_min_ngrams(cities_2))
print (get_min_ngrams(cities_3))
print (get_min_ngrams(cities_4))

输出:

['ter'， 'utr'， 'gro'， 'lem'] ['wol'， 'dam'] ['dam'] ['dam']

1. 创建结构为{'ngram':包含此ngram的城市列表}的字典
2. 1. 找到被大多数城市覆盖的ngram（例如x）（贪心方法），删除此ngram并将其添加到解决方案中
3. 2. 现在我们不必担心上面选择的ngram x所覆盖的城市，因此我们遍历字典并删除由x覆盖的城市。
4. 重复从步骤1开始，直到找不到更多的ngrams

为什么上述解决方案不总是最优的：如其他人所述，上述算法是贪心的，这个问题可以简化为集合覆盖问题，它没有确定性多项式时间解决方案。因此，除非您想赢得100万美元的奖金，否则解决多项式时间算法以获得最佳解决方案是徒劳的。因此，下一个最佳解决方案是贪心的。让我们看看贪心解决方案与最优解决方案相比有多糟糕。

贪心算法有多糟糕：如果有X个城市，如果最佳解决方案是c（即您将需要c ngrams来覆盖所有X个城市），则贪心解决方案不能比c * ln m更差。因此，如果您有50K个城市，则贪心解决方案最多会偏离最优解决方案的10.8197782844倍。

- mujjiga

---

我得到了与你不同的输出。 - Jorden van Foreest

在这个列表中，cities_4 = ['amsterdam'，'walwalwalwaldam']，我得到了['wal'，'dam']。只有['dam']是足够的。 - Jorden van Foreest

@JordenvanForeest 代码中存在一个错误，会添加相同重复的ngrams。我已经修复并更新了输出结果。 - mujjiga

@JordenvanForeest 您是正确的，当我在另一台机器上运行['ter'，'dam'，'wol']时，它会给出不同的输出 :( 我知道问题所在，但很难修复。这个问题与贪婪编程有关。 - mujjiga

这个解决方案可扩展到超过10个城市...而第一个则不行。此解决方案也非常快：在不到2秒的时间内处理超过2500个城市。 - Jorden van Foreest