寻找最佳句子数量和可能解决方案的问题

• 下载工具
• 下载 TextCounter-main - 1 MB
• Github 仓库

引言

为了解释这个问题，假设我们有一个句子列表，例如，一个包含 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);），然后将每个组合与频率表进行比较，使距离最小。因此，将可能组合中的所有频率表相加，并将此总和与目标进行比较，与目标差异最小的组合应被记录。可能有多个组合最接近匹配。

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

背景

这个项目的目的是创建一个工具，用于为给定的语言找到最佳的句子集，该句子集将表示该语言中的所有字符，并将用于记录这些口语句子，作为针对盲人的更大项目的一部分。

应用程序流程

应用程序的使用方法如下

1. 打开应用程序

   

2. 设置目标。当您在“设置”按钮旁边输入一个数字时，它将自动作为所有字符的目标插入，而罕见字符将获得该值的 1/10。然后您可以手动并分别更改这些目标。

   

3. 选择包含 PDF 电子书的文件夹。

   

   然后文件夹路径将显示。

   

4. 然后您就可以开始了。按下“开始”按钮，程序开始运行……

   

5. 优化结果 - 完成书籍阅读后，这些书籍将被分割成句子，并计算和显示其总字符数。然后，当您按下“优化”按钮时，您只会得到其中一些句子，这些句子会将您带到最接近您设置的目标结果。

   

   这就是我们需要改进的地方。

   如您所见，选定句子中每个字符的实际计数与该字符的目标并不足够接近。

   

源代码

代码是在 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;

然后定义Albanian如下

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,
        _T(""),_T(""),-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,0,0,0,0
    };
} CounterTotals;

优化部分

按下“优化”按钮时，将完成实际工作。然后我们需要选择一个句子组合，该组合将使我们最接近目标。

void SentencesCounter::SolveIR(vector<Sentence> &sentences, vector<Sentence> &SelectedData)
{    
    size_t sum = 0;
    vector<Sentence> candidates;
    //========= remove duplicate sentences ===========//
    //set<Sentence> s(candidates.begin(), candidates.end());
    //candidates.assign(s.begin(), s.end());
    //rt(candidates.begin(), candidates.end());
    //candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());
    //unordered_set<int> s;
    unordered_set<wstring> c1;
    for (size_t i = 0; i < sentences.size(); i++) //remove duplicates
    {
        if (sentences[i].text.size() < 10) continue; // to avoid fake sentences

        if (c1.find(sentences[i].text) == c1.end()) { //O(1)
            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<Sentence> selection;
    Sentence sAllSelected;
    ResetSentence(sAllSelected);
    int lastDistance = INT_MAX/2 -1, newDistance = INT_MIN;
    for (auto &s : candidates) // access by reference to avoid copying
    {
        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.AppendFormat(_T("<%s:%d>,"), getAlbaniLetter(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);
}

历史

• 2021年12月17日：初始版本