在处理大量文本数据时,经常需要找到一种方法来选择一组句子,使其字符频率尽可能接近给定的目标频率表。例如,有一个包含1000个句子的列表,这些句子都来自一个装满PDF电子书的文件夹。目标是找到一组句子,其字符频率与给定的频率表尽可能接近。频率表可能如下所示:
{
a: 100,
b: 80,
c: 90,
d: 150,
e: 100,
f: 100,
g: 47,
h: 10,
...
z: 900
}
为了实现这个目标,尝试了各种方法和算法,比如使用组合算法来找出句子列表中所有可能的组合(从comb(1000, 1)到comb(1000, 1000)),然后比较每个组合与频率表的距离,以找到差异最小的组合。然而,计算所有组合需要花费很长时间,通常需要几天时间。因此,迫切需要一种更高效的算法,最好在几分钟内就能完成计算。
这个项目的目的是创建一个工具,用于为给定的语言找到一组最优的句子,这些句子将代表该语言的所有字符,并用于记录这些句子的发音,作为为视障人士提供更大项目的一部分。
应用的使用流程如下:
这就是需要改进的地方。正如看到的,选定句子中每个字符的实际计数与该字符的目标值还不够接近。
代码是在Visual Studio 2017 Enterprise以及MFC中开发的。要运行代码,需要安装MFC。该应用程序是一个基于对话框的应用程序。
首先需要的功能是遍历PDF文件,并从每个文件中提取它包含的文本。这是通过创建的这个源代码库实现的,它基于这个优秀的库。
必须构建代码,使其能够支持阿尔巴尼亚字母表,并且将来可以扩展到其他语言。定义了一个名为Language的结构。
typedef struct {
wchar_t m_CharU[3]{ L"" };
wchar_t m_CharL[3]{ L"" };
int m_Count{ 1 };
int index{ -1 };
} Char;
typedef struct {
wstring LangName;
Char characters[80];
} Language;
Language Albanian = {
L"Albanian",
{
{ _T("A"), _T("a"), 1, 0 },
{ _T("B"), _T("b"), 1, 1 },
{ _T("C"), _T("c"), 1, 2 },
{ _T("Ç"), _T("ç"), 1, 3 },
{ _T("DH"), _T("dh"), 2, 5 },
{ _T("E"), _T("e"), 1, 6 },
{ _T("Ë"), _T("ë"), 1, 7 },
{ _T("F"), _T("f"), 1, 8 },
{ _T("GJ"), _T("gj"), 2, 10 },
{ _T("H"), _T("h"), 1, 11 },
{ _T("I"), _T("i"), 1, 12 },
{ _T("J"), _T("j"), 1, 13 },
{ _T("K"), _T("k"), 1, 14 },
{ _T("LL"), _T("ll"), 2, 16 },
{ _T("M"), _T("m"), 1, 17 },
{ _T("NJ"), _T("nj"), 2, 19 },
{ _T("O"), _T("o"), 1, 20 },
{ _T("P"), _T("p"), 1, 21 },
{ _T("Q"), _T("q"), 1, 22 },
{ _T("RR"), _T("rr"), 2, 24 },
{ _T("SH"), _T("sh"), 2, 26 },
{ _T("TH"), _T("th"), 2, 28 },
{ _T("U"), _T("u"), 1, 29 },
{ _T("V"), _T("v"), 1, 30 },
{ _T("XH"), _T("xh"), 2, 32 },
{ _T("Y"), _T("y"), 1, 33 },
{ _T("ZH"), _T("zh"), 2, 35 },
{ L"", L"", -1, -1 }
}
};
在这个结构中存储了字母表中每个字符的计数:
typedef struct {
int counter[40] {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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
} CounterTotals;
void SentencesCounter::SolveIR(vector &sentences, vector &SelectedData) {
size_t sum = 0;
vector candidates;
//========= remove duplicate sentences ===========//
unordered_set c1;
for (size_t i = 0; i < sentences.size(); i++) {
if (sentences[i].text.size() < 10) continue;
// to avoid fake sentences
if (c1.find(sentences[i].text) == c1.end()) {
c1.insert(sentences[i].text);
candidates.push_back(sentences[i]);
sum += sentences[i].text.length();
}
}
//-----------------------------------------------//
for (size_t i = 0; i < candidates.size(); i++) {
sum += candidates[i].text.length();
}
CalculateValueFactor(sum);
for (size_t i = 0; i < candidates.size(); i++) {
candidates[i].score = GetNewScore(candidates[i]);
}
sort(candidates.begin(), candidates.end(), orderByScoreDistance);
vector selection;
Sentence sAllSelected;
ResetSentence(sAllSelected);
int lastDistance = INT_MAX/2 - 1, newDistance = INT_MIN;
for (auto &s : candidates) {
updateSentence(&sAllSelected, s);
newDistance = GetDistance(sAllSelected, m_target);
if (lastDistance < newDistance) {
for (size_t i = 0; i < 40; i++) {
sAllSelected.counter[i] -= s.counter[i];
}
break;
} else {
selection.push_back(s);
lastDistance = newDistance;
}
}
ResetResults();
CString foundText{ _T("") };
for (auto& sentence : selection) {
foundText.AppendFormat(_T("%s\r\n"), sentence.text.c_str());
UpdateTotals(sentence);
}
for (size_t i = 0; i < 40; i++) {
m_totals.counter[i] = sAllSelected.counter[i];
}
foundText.Append(L"\r\n");
MainDlg* pMainDlg = (MainDlg*)AfxGetApp()->GetMainWnd();
CString temp;
pMainDlg->m_FoundText.GetWindowText(temp);
temp.Append(foundText);
pMainDlg->m_FoundText.SetWindowTextW(temp);
SelectedData.clear();
SelectedData.insert(SelectedData.begin(), selection.begin(), selection.end());
MessageBox(GetForegroundWindow(), L"Selected " + (CString)(std::to_wstring(SelectedData.size()).c_str()) + (CString)L" sentences", L"Result", MB_OK);
}