pandas 串覆盖子串项的极大集

jq6vz3qz  于 2022-11-20  发布在  其他
关注(0)|答案(1)|浏览(163)

我想从许多子串集合中计算一个串的最大覆盖。
这个问题中的所有字符串都是小写的,并且不包含空格或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循环,然后用蛮力强制它。但是这个问题感觉有一个更优的解决方案。或者我到目前为止做了一个小的改变,让它工作。
注意:如果有一个平局-返回第一个是好的。我不太感兴趣返回所有最好的匹配。

unftdfkk

unftdfkk1#

好吧,这不是优化,但让我们开始修复结果。我相信你有两个问题:一是apple中的过计数;另一个是foofoobar0中的少计。
当术语集由两个不重叠的术语(或仅一个术语)组成时,解决第二个问题是容易的:

sum([s.count(t)*len(t) for t in ts])

我会做的。
类似地,当我们有两个重叠项时,我们只取“最好”的一个:

max([s.count(t)*len(t) for t in ts])

因此,我们面临的问题是如何识别两个术语何时重叠。我甚至不考虑包含两个以上术语的术语集,因为只有两个术语的解决方案已经非常慢了:(
让我们定义一个函数来测试重叠:

def terms_overlap(s, ts):
    if ts[0] not in s or ts[1] not in s:
        return False
    start = 0
    while (pos_0 := s.find(ts[0], start)) > -1:
        if (pos_1 := s.find(ts[1], pos_0)) > -1:
            if pos_0 <= pos_1 < (pos_0 + len(ts[0]) - 1):
                return True
        start += pos_0 + len(ts[0])
    start = 0
    while (pos_1 := s.find(ts[1], start)) > -1:
        if (pos_0 := s.find(ts[0], pos_1)) > -1:
            if pos_1 <= pos_0 < (pos_1 + len(ts[1]) - 1):
                return True
        start += pos_1 + len(ts[1])
    return False

准备好该函数后,我们最终可以:

def calc_coverage(strings, tsets):
    for xs, s in enumerate(strings):
        best_cover = 0
        best_ts = 0
        for xts, ts in enumerate(tsets):
            if len(ts) == 1:
                cover = s.count(ts[0])*len(ts[0])
            elif len(ts) == 2:
                if terms_overlap(s, ts):
                    cover = max([s.count(t)*len(t) for t in ts])
                else:
                    cover = sum([s.count(t)*len(t) for t in ts])
            else:
                raise ValueError('Cannot handle term sets of more than two terms')
            if cover > best_cover:
                best_cover = cover
                best_ts = xts
        print(f'{xs}: {s:15} {best_cover:2d} / {len(s):2d} = {best_cover/len(s):8.3f} ({best_ts}: {tsets[best_ts]})')

>>> calc_coverage(my_strings, term_sets)
0: foobar           5 /  6 =    0.833 (0: ['foo', 'ba'])
1: foofoobar0       8 / 10 =    0.800 (0: ['foo', 'ba'])
2: apple            5 /  5 =    1.000 (3: ['apple'])

相关问题