algorithm - 如何在文件的各行中最佳地分配一个词的标记出现？

Question

我有一个包含故事的文本文件，其中每个句子出现在不同的行上，例如:

ONCE UPON A TIME, THERE WAS A MOUSE NAMED ED.
ED WAS A FRIENDLY MOUSE.
HE HAD MANY FRIENDS.
HE LIVED IN A SMALL HOUSE WITH HIS OTHER MOUSE FRIENDS.
HIS MOUSE FRIENDS WERE FRIENDLY.
HIS FRIENDS LIVED IN A SMALL HOUSE.
...

我还创建了一个单词列表，列出了故事中出现的每个单词。

ONCE
UPON
A
TIME
...

这有大约 6,000 个句子，4,000 个不同的单词。

我需要找到一个算法，我将把它写入 BASH 脚本，它最符合这个标准:

1. 单词列表中的每个单词在故事中用大括号恰好标记一次，例如:

   {ONCE} {UPON} {A} {TIME}，{THERE} {WAS} 一只{MOUSE} {NAMED} {ED}。ED 是一只{友好}的老鼠。{HE} {HAD} {MANY} {FRIENDS}。HE {LIVED} {IN} A {SMALL} {HOUSE} {WITH} {HIS} {OTHER} MOUSE FRIENDS。他的鼠标 friend {WERE}友好。他的 friend 住在一个小房子里。...

找到单词的任何位置都可能被标记，例如第一次出现、第三次出现、最后一次出现等。

1. 运行脚本并标记所有单词后，将删除没有大括号的行。在上面的例子中，“他的 friend 住在一个小房子里。”没有大括号，因此该行将被删除。

有些算法会导致很多行被删除。其他算法将导致删除的行数减少。

1. 最佳算法是删除最少行的算法。换句话说，标记词的选择需要最佳地分布在多行中。

这些是我尝试过的算法:

1. 标记故事中每个单词的第一次出现。这导致约 50% 的行被删除，大部分在末尾。

2. 标记故事中每个单词在没有大括号的行中的第一次出现。如果找不到这样的台词，那么这个词在故事中的第一次出现就会被标记出来。这导致约 25% 的行被删除。

3. 随机标记单词。结果可能仍然不是最佳的。

我如何创建一种算法来标记文件中某个单词的一次出现，从而使这些标记尽可能广泛地分布在每一行中，从而使无标记行最少？

Answer 1

准备一个二分图，其中一部分的顶点对应于线，另一部分的顶点对应于词。在一行中单词出现的任何地方放置边缘。找一个maximum matching与，例如，Hopcroft--Karp。对于与单词匹配的每一行，用大括号括起该行中出现的单词。用不匹配的词做一些特别的事情。