查找字符串句子的组合-频率表的组合到目标频率表

下面的文章将解释这个问题。

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

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

[a:100，b:80，c:90，d:150，e:100，f:100，g:47，h:10……z:900]

我想通过使用中的组合从句子列表中找到所有可能的组合这里(so comb(1000，1)；梳(10001000)；)然后将每个组合与频率表进行比较，使得距离最小。因此，对可能组合中的所有频率表求和，并将该和与目标进行比较，应记录与目标差异最小的组合。可能有多个组合最匹配。

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

输入句子：

在储藏场看到的房车比在露营地看到的房车更多。

她尽力帮助他。曾经有几天我希望与自己的身体分离，但今天不是这样的日子。

旋转棒棒糖与流行冰糖有问题。

两人沿着狭槽峡谷走去，没有注意到远处的雷声。

州际公路两旁长满了成片的杏仁树，这让疯狂的驾车狂们赞不绝口。

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

风滚草拒绝翻滚，但更愿意腾跃。

她很反感他分不清柠檬水和>石灰。

他不想去看牙医，但他还是去了。

查找与以下频率表最匹配的句子组合：

[a: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]

频率表上下相等，不包括特殊字符。

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

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

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

贪婪算法

你第一个测试所有可能的句子组合的想法太慢了。如果你有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")。

显然，最佳解决方案是用字母表的两半完美地覆盖目标。但是我们的贪婪算法将选择"；快速棕色狐狸"；句子第一，因为它有更高的分数。

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代码

这可以简化为与目标问题具有最小绝对差的子序列和。

问题如下：您有一个具有整数值的数组A，比如[1,5,3,2,6]，以及一个整数值T，即目标。您希望从A中找到元素的子序列A'，以使abs(target - sum(A'))最小化。

在您的情况下，A的单个整数值是二维的，其中它们包含每个句子的字符频率表，目标也是二维的，因为它包含字符计数。您希望最小化绝对差的总和。

这显然是一个动态编程问题。如果没有优化，时间复杂度将是指数级的，我们需要检查2^n的可能性(对于每个元素，我们有两种可能性：要么接受，要么离开)。我想这就是你在问题中提到的，通过创建所有组合。

但通过优化，我们可以实现n * T，其中n是A中的元素数量，T是目标值。当然，如果我们只想要最接近的数字本身，而不是求和该数字的元素，那么这就是问题所在。

要获得子序列本身的元素，从而获得最佳解决方案，您有两个选项：

回溯，它具有前面解释的指数时间复杂性
DP，其中时间复杂度如上所述保持可管理

这些问题和算法是众所周知的，我认为它们不需要解释。

据我所知，你的具体问题是如何映射到这个问题的，这也是显而易见的。当然，你想如何实现它也有一些复杂性。但如果你的问题和上面描述的子序列和问题之间的关系不清楚，请告诉我，这样我就可以进一步解释了。

以下是我发现的一些链接，可以帮助你解决这个问题。请注意，它们不是一个直截了当的答案，因为这个问题相对复杂。

LeetCode上的最近子序列和问题。这可以处理这样的情况，即你只寻找最接近的和，而不是通往那个和的路径。讨论页面上充满了不同的想法和详细的解释(按大多数选票排序)

DP和路径重建：这是关于DP系列的一部分

DP底漆

重构最优解的路径

我们试图找到本文中显示的解决方案，但我认为该解决方案不好。https://www.codeproject.com/Articles/5320281/A-problem-finding-optimal-number-of-sentences-and

在我看来，这就像是一个高级的knapsack问题。输入大小的上限(1000)也有帮助，因为看起来，O(n^2)复杂性在这里应该是可以接受的。

在标准背包问题中，您有两个输入，value and weight和一个limit，您可以将total weight携带到其中，从而使total value最大化。

在这里，您的限制将是target频率表，例如

[a:100, b:80, c:90, d:150, e:100, f:100, g:47, h:10 ..... z:900]

输入weights将是单个句子的频率表，例如，在你给出的10个句子的例子中，不要把输入看作句子，而是按照以下方式查看输入：

More RVs were seen in the storage lot than at the campground ->
{'m': 2, 'o': 4, 'r': 5, 'e': 8, 'v': 1, 's': 3, 'w': 1, 'n': 4, 'i': 1, 't': 6, 'h': 3, 'a': 4, 'g': 2, 'l': 1, 'c': 1, 'p': 1, 'u': 1, 'd': 1}
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 ->
{'s': 8, 'h': 9, 'e': 16, 'd': 8, 'i': 4, 'r': 4, 'b': 5, 't': 9, 'o': 8, 'l': 1, 'p': 2, 'm': 3, 'a': 7, 'v': 1, 'n': 4, 'y': 5, 'w': 3, 'f': 2, ',': 1, 'u': 1, '’': 1}
The swirled lollipop had issues with the pop rock candy ->
{'t': 3, 'h': 4, 'e': 4, 's': 4, 'w': 2, 'i': 4, 'r': 2, 'l': 4, 'd': 3, 'o': 4, 'p': 4, 'a': 2, 'u': 1, 'c': 2, 'k': 1, 'n': 1, 'y': 1}
...
...
...
He didn’t want to go to the dentist, yet he went anyway ->
{'h': 3, 'e': 6, 'd': 3, 'i': 2, 'n': 5, 't': 9, 'w': 3, 'a': 3, 'o': 3, 'g': 1, 's': 1, 'y': 3}
and so on...

现在，在这种情况下，我们没有values列表，在标准背包的情况下，需要最大化该列表。我们的value将仅从组合频率表中导出，因为我们的miximisation条件是min differential of the target freq table and combined freq table。我们需要一个函数来满足这种最大化条件，而不是正常的添加来最大化。

注意：在写这个答案的时候，我假设你已经了解DP和标准背包算法。如果没有，你真的需要先研究一下，因为这是这个解决方案的基础。

注2：答案中肯定有一些内容我可以进一步阐述。如果有任何不清楚或需要明确解释的地方，请随时在评论中询问，我很乐意编辑回复。

贪婪算法

贪婪算法的非最优性

相关内容

最新更新

热门标签：