我想从许多子串集合中计算一个串的最大覆盖。
这个问题中的所有字符串都是小写的，并且不包含空格或Unicode奇怪的字符串。
因此，给定一个字符串：abcdef，以及两组字符串：['abc', 'bc'], ['abc', 'd']，第二个组（['abc', 'd']）覆盖了原始字符串的更多部分。顺序对于精确匹配很重要，因此术语组['fe', 'cba']不会与原始字符串匹配。
我有一个大的字符串集合，和一个大的术语组集合。所以如果可能的话，我希望实现得更快一点。
我已经在Python中尝试了下面的例子。我使用了Pandas和Numpy，因为我认为它可能会加快一点速度。我还遇到了一个过度计数的问题，你会在下面看到。
import re
import pandas as pd
import numpy as np
my_strings = pd.Series(['foobar', 'foofoobar0', 'apple'])
term_sets = pd.Series([['foo', 'ba'], ['foo', 'of'], ['app', 'ppl'], ['apple'], ['zzz', 'zzapp']])
# For each string, calculate best proportion of coverage:
# Try 1: Create a function for each string.
def calc_coverage(mystr, term_sets):
# Total length of string
total_chars = len(mystr)
# For each term set, sum up length of any match. Problem: this over counts when matches overlap.
total_coverage = term_sets.apply(lambda x: np.sum([len(term) if re.search(term, mystr) else 0 for term in x]))
# Fraction of String covered. Note the above over-counting can result in fractions > 1.0.
coverage_proportion = total_coverage/total_chars
return coverage_proportion.argmax(), coverage_proportion.max()
my_strings.apply(lambda x: calc_coverage(x, term_sets))这将导致：
0 (0, 0.8333333333333334)
1 (0, 0.5)
2 (2, 1.2)这就带来了一些问题。我看到的最大的问题是重叠的项被分开计算，这导致了1.2或120%的覆盖率。
我认为理想的输出应该是：
0 (0, 0.8333333333333334)
1 (0, 0.8)
2 (3, 1.0)我想我可以写一个double for循环，然后用蛮力强制它。但是这个问题感觉有一个更优的解决方案。或者我到目前为止做了一个小的改变，让它工作。
注意：如果有一个平局-返回第一个是好的。我不太感兴趣返回所有最好的匹配。
1条答案
按热度按时间unftdfkk1#
好吧，这不是优化，但让我们开始修复结果。我相信你有两个问题：一是
apple中的过计数;另一个是foofoobar0中的少计。当术语集由两个不重叠的术语（或仅一个术语）组成时，解决第二个问题是容易的：
我会做的。
类似地，当我们有两个重叠项时，我们只取“最好”的一个：
因此，我们面临的问题是如何识别两个术语何时重叠。我甚至不考虑包含两个以上术语的术语集，因为只有两个术语的解决方案已经非常慢了：（
让我们定义一个函数来测试重叠：
准备好该函数后，我们最终可以：