查找字符串语句的组合.频率表到目标频率表的组合

Question

这个问题在下面是文章中作了解释。

我有一个句子列表，例如1000句句子的列表。

我想找一个句子组合来匹配/“最接近”某个频率表：

答:100，b:80，c:90，d:150，e:100，f:100，g:47，h:10 .z:900

我考虑从句子列表中找到所有可能的组合，比如在这里中使用组合(所以梳(1000，1)；梳(1000,1000)；然后将每一个组合与频率表进行比较，这样距离就最小了。因此，从一个可能的组合和所有的频率表，并比较这个和与目标，组合与最小的差异与目标应该被记录。可能有多个最匹配的组合。

问题是，所有组合的计算时间太长，显然要花几天时间才能完成。是否有一种已知的算法可以有效地解决这一问题？最理想的情况是最多几分钟？

输入句子：

在仓库里看到的越野车比在营地看到的要多。她尽力帮助他。曾经有一些日子，我希望与我的身体分离，但今天不是其中的一天。旋转的棒棒糖与流行糖果有问题。两个人沿着缝隙峡谷走去，没有注意远处的雷声。州际公路两旁排列着一片片杏仁树，这是对疯狂驾驶坚果的赞扬。他不是詹姆斯·邦德，他的名字是罗杰·摩尔。卷尾草拒绝倒下，但更愿意炫耀。她很反感，他看不出柠檬水和石灰水的区别.他不想去看牙医，但还是去了。

查找与以下频率表最接近的句子组合：

答:5，b:5，c:5，d:5，e:5，f:5，g:5，h:5 .z:5

示例：

第六句频率表

他不是詹姆斯·邦德，他的名字是罗杰·摩尔。

a:2，e:5，g:1，h:1，i:3，j:1，m:3，n:3，o:5，r:3，s:4

频率表取上、下相等，不包含特殊字符。

Answer 1

每当有人从以下5%以上或以下的句子中找到3c、3a、3b、3d或30c、30a、30b、30d的组合句时，就可以解决这个问题。

S1: aaaaaaaaaaaaaaaaaa bbbbbb c
S2: aaaaaaaa bbbbbbbb d
S3: aaaaaaaaaaa bbbbbbbbb c dd
S4: aaaaaaaaaa bbbbbbbb 

现实点。没有解决方案，没有NP-硬也没有NP-完全，没有解决方案。一个句子中字母的出现数(例如，像i或a这样的元音)不等于其他的字母(如x或w)。我们可以找到最好的匹配，如提供的代码这里或更改需求。我试着用KnapSack算法和欧几里得距离和标准差来解决这个问题，但是没有人给我这样的答案，因为没有一个字母大小相同的句子。

Answer 2

贪婪算法

你测试所有可能的句子组合的第一个想法太慢了。如果你有n句子，那么就会有2**n (2到n的幂)可能的句子组合。例如，在n=1000中，有2**1000 ≈ 10**300可能的组合。那是一个1，后面是300个零:比宇宙中粒子的数量还要多，比国际象棋中可能出现的不同游戏的数量还要多！

这里有一个关于贪婪算法的建议。它不是特别优化，它的运行时间是O(k * n**2)，其中n是句子的数量，k是最长的句子的长度。

其想法如下：

• 将分数number of useful characters - number of superfluous characters属性赋于每个句子。例如，如果一个句子包含20 'a'，而目标只需要15 'a'，那么我们将计算出15个有用的'a'和5个多余的'a'，因此字符'a'贡献了这个句子的分数10。
• 在结果中添加得分最高的句子；
• 更新目标以删除结果中已经存在的字符；
• 更新每个句子的得分以反映更新的目标。
• 循环，直到没有一个句子有一个正面的分数。

我太懒于在C++中实现它，所以这里是用最大堆和计数器实现的python。在编写完代码之后，我编写了一个快速解释，以帮助您将其转换为C++。

from collections import Counter
import heapq

sentences = ['More RVs were seen in the storage lot than at the campground.', 'She did her best to help him.', 'There have been days when I wished to be separated from my body, but today wasn’t one of those days.', 'The swirled lollipop had issues with the pop rock candy.', 'The two walked down the slot canyon oblivious to the sound of thunder in the distance.', 'Acres of almond trees lined the interstate highway which complimented the crazy driving nuts.', 'He is no James Bond; his name is Roger Moore.', 'The tumbleweed refused to tumble but was more than willing to prance.', 'She was disgusted he couldn’t tell the difference between lemonade and limeade.', 'He didn’t want to go to the dentist, yet he went anyway.']

target = Counter('abcdefghijklmnopqrstuvwxyz' * 10)
Counter({'a': 10, 'b': 10, 'c': 10, 'd': 10, 'e': 10, 'f': 10, 'g': 10, 'h': 10, 'i': 10, 'j': 10, 'k': 10, 'l': 10, 'm': 10, 'n': 10, 'o': 10, 'p': 10, 'q': 10, 'r': 10, 's': 10, 't': 10, 'u': 10, 'v': 10, 'w': 10, 'x': 10, 'y': 10, 'z': 10})

print(target)

counts = [Counter(''.join(filter(str.isalpha, s)).lower()) for s in sentences]  # remove punctuation, spaces, uncapitalize, then count frequencies

def get_score(sentence_count, target):
    return sum((sentence_count & target).values()) - sum((sentence_count - target).values())

candidates = []
for sentence, count in zip(sentences, counts):
    score = get_score(count, target)
    candidates.append((-score, sentence, count))

heapq.heapify(candidates)    # order candidates by score
                             # python's heapq only handles min-heap
                             # but we need a max-heap
                             # so I added a minus sign in front of every score

selection = []
while candidates and candidates[0][0] < 0:  # while there is a candidate with positive score
    score, sentence, count = heapq.heappop(candidates)  # greedily selecting best candidate
    selection.append(sentence)
    target = target - count                             # update target by removing characters already accounted for
    candidates = [(-get_score(c,target), s, c) for _,s,c in candidates]  # update scores of remaining candidates
    heapq.heapify(candidates)                       # reorder candidates according to new scores

# HERE ARE THE SELECTED SENTENCES:
print(selection)
# ['Acres of almond trees lined the interstate highway which complimented the crazy driving nuts.', 'There have been days when I wished to be separated from my body, but today wasn’t one of those days.']

# HERE ARE THE TOTAL FREQUENCIES FOR THE SELECTED SENTENCES:
final_frequencies = Counter(filter(str.isalpha, ''.join(selection).lower()))
print(final_frequencies)
# Counter({'e': 22, 't': 15, 'a': 12, 'h': 11, 's': 10, 'o': 10, 'n': 10, 'd': 10, 'i': 9, 'r': 8, 'y': 7, 'm': 5, 'w': 5, 'c': 4, 'b': 4, 'f': 3, 'l': 3, 'g': 2, 'p': 2, 'v': 2, 'u': 2, 'z': 1})

# CHARACTERS IN EXCESS:
target = Counter('abcdefghijklmnopqrstuvwxyz' * 10)
print(final_frequencies - target)
# Counter({'e': 12, 't': 5, 'a': 2, 'h': 1})

# CHARACTERS IN DEFICIT:
print(target - final_frequencies)
# Counter({'j': 10, 'k': 10, 'q': 10, 'x': 10, 'z': 9, 'g': 8, 'p': 8, 'u': 8, 'v': 8, 'f': 7, 'l': 7, 'b': 6, 'c': 6, 'm': 5, 'w': 5, 'y': 3, 'r': 2, 'i': 1})

解释：

• Python的Counter( )将句子转换为映射character -> frequency；
• 对于两个计数器a和b，a & b是多集交点，a - b是多集差；
• 对于计数器a，sum(a.values())是总计数(所有频率之和)；
• heapq.heapify将列表转换为最小堆，这是一种数据结构，允许以最小的分数轻松访问元素。我们实际上希望句子有最大的分数，而不是最小，所以我用负数替换了所有的分数。

贪婪算法的非最优性

我应该指出，这个贪婪的算法是一种近似算法。在每一次迭代中，它都选择得分最高的句子；但并不能保证最优解实际上包含该句子。

建立一个贪婪算法找不到最优解的示例很容易：

target = Counter('abcdefghijklmnopqrstuvwxyz')
print(target)
# Counter({'a': 1, 'b': 1, 'c': 1, 'd': 1, 'e': 1, 'f': 1, 'g': 1, 'h': 1, 'i': 1, 'j': 1, 'k': 1, 'l': 1, 'm': 1, 'n': 1, 'o': 1, 'p': 1, 'q': 1, 'r': 1, 's': 1, 't': 1, 'u': 1, 'v': 1, 'w': 1, 'x': 1, 'y': 1, 'z': 1})

sentences = [
    'The quick brown fox jumps over the lazy dog.',
    'abcdefghijklm',
    'nopqrstuvwxyz'
]

对于这一目标，分数如下：

[
    (17, 'The quick brown fox jumps over the lazy dog.'),
    (13, 'abcdefghijklm'),
    (13, 'nopqrstuvwxyz')
]

这两个“半字母”各有13分，因为它们包含13个字母。“飞快的棕色狐狸”这句话分数为17 =26-9，因为它包含26个字母，加上9个多余的字母(例如，有3个多余的'o‘和2个多余的'e')。

最优的解决方案，很明显，是用字母的两半覆盖目标。但是我们的贪婪算法会首先选择“快棕狐”这个句子，因为它的分数更高。

Answer 3

typedef struct
{
    wstring text{ L"" };            
    vector<int> encoded_text;
    int counter[26] // frequency table
    {
        0,0,0,0,0,
        0,0,0,0,0,
        0,0,0,0,0,
        0,0,0,0,0,
        0,0,0,0,0,
        0,
    };

    int score = INT_MIN;

} Sentence;  

 
int m_target[26]
{
    10,10,10,10,10,
    10,10,10,10,10,
    10,10,10,10,10,
    10,10,10,10,10,
    10,10,10,10,10,
    10
};

bool orderByScore(const Sentence &a, const Sentence &b)
{
    return b.score < a.score;
}

int SentencesCounter::GetScore(Sentence sentence, int* target)
{
    int sum1 = 0;
    int sum2 = 0;

    for (size_t i = 0; i < 26; i++)
    {
        int sentenceFreq = sentence.counter[i];
        int targetFreq = target[i];

        sum1 += min(sentenceFreq, targetFreq);
        sum2 += max(0, sentenceFreq - targetFreq);
    }

    return sum1 - sum2;
}

vector<Sentence> SentencesCounter::SolveSO(vector<Sentence> &sentences)
{
    vector<Sentence> candidates{ sentences };

    for (size_t i = 0; i < candidates.size(); i++)
    {
        candidates[i].score = GetScore(candidates[i], m_target);
    }

    sort(candidates.begin(), candidates.end(), orderByScore);

    int target[26];
    memcpy(target, m_target, 26 * sizeof(int));

    vector<Sentence> selection;
    while (candidates.front().score > 0) // while there is a candidate with positive score
    {
        Sentence s = candidates.front();
        if(s.encoded_text.size() > 0) selection.push_back(s);
        candidates.front().score = INT_MIN;

        for (size_t i = 0; i < 26; i++) { target[i] -= s.counter[i]; } // update target

        size_t i;
        for (i = 0; i < candidates.size(); i++)
        {
            if (candidates[i].score > INT_MIN) // int min means already added to selection
                candidates[i].score = GetScore(candidates[i], target);
            else if (i != 0) break; // int min found at other index than top
        }

        partial_sort(candidates.begin(), candidates.begin() + i, candidates.end(), orderByScore);
    }
    return selection
}

尝试在psuedo CPP中从Stef复制Python代码