给定单词列表，如何找到唯一词缀列表？
How to find list of unique affixes given a list of words?
词缀可以是前缀（词前）、中缀（词中）或后缀（词后）。我有一个 list of 200k+ latin/greek names used in biological taxonomy. It turns out there is no centralized list of all the affixes used in the taxonomy, unfortunately, other than this very basic list.
问题是，我怎样才能将 200k+ 的 latin/greek 名称列表分成词缀列表（最好只使用普通的 JavaScript）？
我真的不知道从哪里开始。如果我构造一个 trie，我需要以某种方式测试特定的词块。或者，如果可以扩展该块，则在我们达到某种最终扩展之前不要包含该块...
const fs = require('fs')
const words = fs.readFileSync(`/Users/lancepollard/Downloads/all.csv`, 'utf-8').trim().split(/\n+/)
const trie = { children: {} }
words.forEach(word => addToTrie(trie, word))
function addToTrie(trie, word) {
let letters = word.trim().split('')
let node = trie
let i = 0
while (i < letters.length) {
let letter = letters[i++]
node = node.children[letter] = node.children[letter] || { children: {} }
}
node.isWord = true
}
它不需要精确，就像每个词缀实际上都意味着什么，它可能是脏的（在那种情况下，有些词有某种意义，有些词没有）。但它不应该只列出单词字母的每一种排列之类的东西。它应该包括“潜在词缀候选”的东西，它们是在列表中出现不止一次的块。这至少会让我到达那里，然后我可以手动浏览并查找每个“块”的定义。理想情况下，它还应该指出它是否是 prefix/infix/suffix。也许输出是 CSV 格式 affix,position.
您可以在如何解决这个问题上发挥创意，因为如果事先不知道可能的词缀列表，我们就不知道确切的输出应该是什么。这基本上是尝试 找到 尽可能最好的词缀。例如，如果它包含像 aa- 这样的前缀，这可能是一个常见的字母序列，但我认为它不是词缀，这对我来说很好，它可以手动过滤掉。但是如果有两个词（我编的），比如 abrogati 和 abrowendi，那么 abro 将是一个“公共前缀”，并且应该包含在最终列表中，而不是 abr、ab 和 a，尽管它们也很常见。基本上，最长的公共前缀。然而，如果我们有单词 apistal 和 ariavi，我们可以说 a 是一个公共前缀，所以我们的最终列表将包括 a 和 abro .
更详细一点，假设我们有这两个词 aprineyanilantli 和 aboneyanomantli，它们有共同的前缀 a- 和共同的后缀 -antli ，以及中缀 -neyan-，因此它们应该在最终列表中。
它不一定需要高效，因为理论上这只会 运行 一次，在 200k+ 列表上。但如果它也有效率，那将是额外的好处。理想情况下，运行 应该不需要几个小时，但我不确定什么是可能的:)
另一个例子是这样的：
brevidentata
brevidentatum
brevidentatus
crassidentata
crassidentatum
crassidentatus
这里，前3个有共同的前缀，brevidentat，然后2-3有共同的前缀brevidentatu。但后来（根据人类知识），我们发现 identat 可能是我们想要的 infix，而 a/um/us是单词形式的后缀。另外，我们看到 identat 是 crass... 和 brev... 这两个词的中缀。所以最终结果应该是：
brav-
crass-
-identat-
-a
-us
-um
从理论上讲，这将是理想的结果。但你也可以这样：
brav-
crass-
-identat-
-identata
-identatus
-identatum
这也行，我们可以做一些简单的过滤，稍后再过滤掉。
注意，我不关心 环绕 其他东西的单词部分意义上的中缀，比如 stufffoo...barstuff，其中 foo...bar 包裹了一些东西。我只关心重复的单词部分，比如前缀、后缀、单词中间的东西。
这里有一个简单的方法，不过大概是在小时内。此外，您可以在 JavaScript 中执行此操作，但我将采用通用的 Unixy 方法，您可以用任何语言编写该方法，因为这很容易考虑。
首先，让我们获取您的文件，并在每个单词的 start/end 和字母之间的 space 处添加标记。所以你的例子会变成：
^ b r e v i d e n t a t a $
^ b r e v i d e n t a t u m $
^ b r e v i d e n t a t u s $
^ c r a s s i d e n t a t a $
^ c r a s s i d e n t a t u m $
^ c r a s s i d e n t a t u s $
这是我们的一般表示，space 分隔可能的词缀。基本词缀是字母、开始和结束。当然，这里我们没有找到词缀。
这是单个词缀搜索过程的样子。
拿我们的文件，创建 tempfile 个不同的可能词缀部分，然后是单词的行号。 （我说 distinct 这样如果行 666 包含 a b a b 你就不会得到 a b: 666 两次。）所以我们的文件开始于：
^ b: 1
^ b r: 1
.
.
.
^ c r a s s i d e n t a t u s $: 6
接下来我们 sort 文件（只需使用 Unix LC_ALL=C sort tempfile > sortedtempfile 命令，LC_ALL 强制进行 asciibetical 排序）。您现在生成 sortedtempfile 开始于：
^ b: 1
^ b: 2
.
.
.
^ c r a s s i d e n t a t u s $: 6
下一个 运行 一个自定义命令，为每个至少出现 2 次的前缀指定您将其用作词缀保存的符号数，然后是词缀，然后是列表它出现的地方。这会生成一个文件 tempsaved，开始于：
3: ^ b: 1 2 3
6: ^ b r e: 1 2 3
.
.
.
16: v i d e n t a t u: 2 3
现在执行 sorted -rn tempsaved > sortedtempsaved 从最大节省排序，首先找到最大节省。此文件现在开始
36: ^ c r a s s i d e n t a t: 4 5 6
33: ^ b r e v i d e n t a t: 1 2 3
36: ^ c r a s s i d e n t a: 4 5 6
在下一个函数中，我们识别词缀，直到在同一行号上遇到 2 个词缀。然后返回到我们的原始文件并应用它们。因此，在此遍中，我们将确定 ^crassidentat 和 ^brevidentat。然后生成一个新文件，其中包含：
^brevidentat a $
^brevidentat u m $
^brevidentat u s $
^crassidentat a $
^crassidentat u m $
^crassidentat u s $
现在重复。
在您的示例中，您将得到以下一组词缀：
^crassidentat
^brevidentat
um$
us$
a$
如果您将单词 identata、identatum 和 identatus 添加到原始列表，相同的算法将生成以下词缀列表
identat
^crass
^brev
um$
us$
a$
这是你所说的理想结果。
我的信封背面说您应该预计每次通过需要几分钟时间。但是我们试图在每次通过时找到很多词缀。所以我预计这不会超过几十次。此外，该列表之后还需要人工审核。我认为没有什么可以避免的。
前缀和后缀使用 Trie 很容易。但是，Trie 不会帮助您处理中缀。
Trie 示例代码（在 Java 中，未经测试，不完整）
class Node {
private int cnt;
private Map<Character, Node> children;
Node() {
cnt = 0;
this.children = new HashMap<>();
}
Node(String s, int pos) {
this();
addChild(s, pos);
}
bool isLeaf() {
return this.children.size() == 0
}
void addChild(String s, int pos) {
if (pos == s.length()) {
return;
}
char c = s.charAt(pos);
if (children.containsKey(c)) {
children.get(c).addChild(s, pos + 1);
} else {
children.put(c, new Node(s, pos + 1));
}
cnt++;
}
void removeChild(char c) {
int ccnt = 0;
Node child = children.remove(c);
if (child != null) {
ccnt = child.cnt;
}
cnt -= ccnt;
}
// other methods as necessary for traversal/value lookup...
}
class Solution {
private Node preroot = new Node();
private Node sufroot = new Node();
void addWord(String s) {
preroot.addChild(s, 0);
sufroot.addChild(new StringBuilder(s).reverse().toString(), 0);
}
void findPrefixes(int minOccur) {
// standard tree traversal on preroot,
// starting at the left-most leaf.
// when it finds a non-leaf with cnt >= minOccur
// output all permutations and remove the child.
}
}
中缀
中缀的问题是你不知道从哪里开始。
即采用字符串 abcdefgh 和 pppbcdefgzzzz，它们具有共同的中缀 bcdefg。此外，abcdefgh 和 pppabcdefgzzz 怎么样？
要解决这个问题，您基本上需要将单词分解成所有可能的成分，然后指向单词。
然后遍历印章列表，按长度降序排序，并删除与“使用过”的单词相关的所有条目。
即abc 将成为查找条目：abc、ab、bc、a、b、c。
然后查找 table 看起来像：
单词与符号的关联：
{abc -> {abc, ab, bc, a, b, c}}
地图：
{abc -> { abc }}
{ab -> { abc }}
{bc -> { abc }}
{a -> { abc }}
{b -> { abc }}
{c -> { abc }}
当我们添加 bcd 时，它会添加符号：bcd、bc、cd、b、c、d，添加单词关联并更新查找 table：
{abc -> { abc }}
{bcd -> { bcd }}
{ab -> { abc }}
{bc -> { abc, bcd }}
{cd -> { bcd }}
{a -> { abc }}
{b -> { abc, bcd }}
{c -> { abc, bcd }}
{d -> { bcd }
然后使用映射键的长度来指定排序顺序。从顶部开始，导航直到达到最少出现次数，然后使用该列表中的单词并从结构中删除单词。从映射中删除单词使用之前保存的单词关联来查找符号映射中的键。
这是一个有趣的问题，我有一个解决方案的草图，其中包含 运行 可用的代码和一些合理的——但远非完美的——输出。使用变体即使不是很快，也很容易。
想法是首先 运行 遍历所有单词，以各种可能的方式拆分它们，然后计算所有单词中每个前缀、中缀和后缀的出现次数，最后使用它信息以及评分函数，以选择每个单词的最佳表示。
我测试过的评分函数涉及前缀长度、该前缀在所有单词中的计数以及后缀和词缀的相同因素的组合。一般来说，我对长度的权衡远大于对数量的权衡，现在我主要关注前缀，只稍微权衡后缀。
运行 这需要几分钟，但比 Node 默认获得的内存多。我运行它作为
node --max-old-space-size=8192 index
这似乎就足够了。我还没有用 4GB 试过。
我的代码看起来像这样，最近的（也是我最喜欢的）评分函数：
const {readFile, writeFile} = require ('fs') .promises
const range = (lo, hi) =>
Array .from ({length: hi - lo}, (_, i) => i + lo)
const chooseTwo = (n) =>
range (0, n) .flatMap (i => range (i + 1, n + 1) .map (j => [i, j]))
const maximumBy = (fn) => (xs) =>
xs .reduce ((max, x) => {
const xScore = fn (x);
return xScore > max .score ? {score: xScore, val: x} : max;
}, {score: -Infinity}) .val
const breakdown = (word) => {
const len = word.length;
const ranges = chooseTwo (len);
return [
... ranges .map (([i, j]) => ({p: word .slice (0, i), i: word .slice (i, j), s: word .slice (j)})),
... range (0, len - 1) .map (i => ({p: '', i: word .slice (0, i), s: word .slice (i)})),
];
}
const score = (counts) => ({p, i, s}) =>
Math .max (1, Math .sqrt (1 + counts .prefixes [p]) * p .length ** 2) *
// Math .max (1, counts .infixes [i] * i .length ) *
Math .max (1, counts .suffixes [s] * s .length)
const process = (words) => {
const breakdowns = words .map (breakdown)
const counts = breakdowns .reduce (
(all, breakdown) => breakdown .reduce (
(all, {p, i, s}) => {
all .prefixes [p] = (all .prefixes [p] || 0) + 1;
all .infixes [i] = (all .infixes [i] || 0) + 1;
all .suffixes [s] = (all .suffixes [s] || 0) + 1;
return all;
},
all
),
{prefixes: {}, infixes: {}, suffixes: {}}
)
return breakdowns .map (maximumBy (score (counts)))
}
readFile ('./all.csv', 'utf8')
.then (s => s.split ('\n'))
.then (process)
.then (breakdowns => breakdowns .map (({p, i, s}) => `${p ? `(${p}-)` : ''}(${i})${s ? `(-${s})` : ''}`))
.then (words => writeFile ('./res.csv', words .join ('\n')), 'utf8')
.then (() => console .log ('Result written'))
第一个重要的函数是breakdown，例如，将'horse'变成：
(h)(-orse)
(ho)(-rse)
(hor)(-se)
(hors)(-e)
(horse)
(h-)(o)(-rse)
(h-)(or)(-se)
(h-)(ors)(-e)
(h-)(orse)
(ho-)(r)(-se)
(ho-)(rs)(-e)
(ho-)(rse)
(hor-)(s)(-e)
(hor-)(se)
(hors-)(e)
()(-horse)
(h)(-orse)
(ho)(-rse)
(hor)(-se)
(h-)(orse)
(ho-)(rse)
(hor-)(se)
(hors-)(e)
与 p、i 和 s 属性在内部存储，用于 prefix、infix 和 suffix，所以它实际上看起来像这样：
[
{p: '', i: 'h', s: 'orse'},
{p: '', i: 'ho', s: 'rse'},
{p: '', i: 'hor', s: 'se'},
{p: '', i: 'hors', s: 'e'},
{p: '', i: 'horse', s: ''},
{p: 'h', i: 'o', s: 'rse'},
{p: 'h', i: 'or', s: 'se'},
{p: 'h', i: 'ors', s: 'e'},
{p: 'h', i: 'orse', s: ''},
{p: 'ho', i: 'r', s: 'se'},
{p: 'ho', i: 'rs', s: 'e'},
{p: 'ho', i: 'rse', s: ''},
{p: 'hor', i: 's', s: 'e'},
{p: 'hor', i: 'se', s: ''},
{p: 'hors', i: 'e', s: ''},
{p: '', i: '', s: 'horse'},
{p: '', i: 'h', s: 'orse'},
{p: '', i: 'ho', s: 'rse'},
{p: '', i: 'hor', s: 'se'},
{p: 'h', i: 'orse', s: ''},
{p: 'ho', i: 'rse', s: ''},
{p: 'hor', i: 'se', s: ''},
{p: 'hors', i: 'e', s: ''},
]
breakdown 建立在两个简单的函数上：range 创建一个整数范围，开始时包含在内，结束时不包含，因此 range (3, 12) 产生 [3, 4, 5, 6, 7, 8, 9, 10, 11] . chooseTwo 找到 0 和 n 之间的所有不同整数对。
我们的第二个主要功能是 process，它使用 breakdown 和 maximumBy 执行上述算法，我们使用 [=34= 选择最大值细分] 功能。在这两者之间，我们简单地计算使用的零件。
这就是所有基础设施。重要工作在 score。您可以通过多种方式更改它。如果不是假期时间，我很想尝试一下这个的变体。但是，当您这样做时，您应该注意，尽管使用一小部分数据很容易获得看起来合理的结果，但对于完整数据而言，这并不总是如此合理。因此，您将需要 运行 具有各种功能的完整代码。
我建议调查的一件事是是否有一个相当准确的英语预测断字工具——不是基于字典的，而是合理的第一原则或一些机器学习的结果 运行s。一个好的断字决定可能会帮助您编写更好的评分函数。
如果您想在一小部分数据中看到这一点，您可以扩展以下代码段：
const range = (lo, hi) =>
Array .from ({length: hi - lo}, (_, i) => i + lo)
const chooseTwo = (n) =>
range (0, n) .flatMap (i => range (i + 1, n + 1) .map (j => [i, j]))
const maximumBy = (fn) => (xs) =>
xs .reduce ((max, x) => {
const xScore = fn (x);
return xScore > max .score ? {score: xScore, val: x} : max;
}, {score: -Infinity}) .val
const breakdown = (word) => {
const len = word.length;
const ranges = chooseTwo (len);
return [
... ranges .map (([i, j]) => ({p: word .slice (0, i), i: word .slice (i, j), s: word .slice (j)})),
... range (0, len - 1) .map (i => ({p: '', i: word .slice (0, i), s: word .slice (i)})),
];
}
const score = (counts) => ({p, i, s}) =>
Math .max (1, Math .sqrt (1 + counts .prefixes [p]) * p .length ** 2) *
// Math .max (1, counts .infixes [i] * i .length ) *
Math .max (1, counts .suffixes [s] * s .length)
const process = (words) => {
const breakdowns = words .map (breakdown)
const counts = breakdowns .reduce (
(all, breakdown) => breakdown .reduce (
(all, {p, i, s}) => {
all .prefixes [p] = (all .prefixes [p] || 0) + 1;
all .infixes [i] = (all .infixes [i] || 0) + 1;
all .suffixes [s] = (all .suffixes [s] || 0) + 1;
return all;
},
all
),
{prefixes: {}, infixes: {}, suffixes: {}}
)
return breakdowns .map (maximumBy (score (counts)))
}
const words = ["cristata", "cristatella", "cristatellidae", "cristatellus", "cristaticeps", "cristaticollis", "cristatiforme", "cristatifrons", "cristatigena", "cristatipes", "cristatispinosa", "cristatissimus", "cristatogobius", "cristatoides", "cristatolabra", "cristatopalpus", "cristatula", "cristatum", "cristatus", "cristavarius", "cristellaria", "cristeremaeus", "cristi", "cristianalemani", "cristiani", "cristibrachium", "cristicauda", "cristiceps", "cristicola", "cristicollis", "cristidigitus", "cristifer", "cristifera", "cristiferus", "cristiformis", "cristifrons", "cristigera", "cristiglans", "cristiloba", "cristimanus", "cristina", "cristinae", "cristipalpis", "cristipes", "cristirhizophorum", "cristis", "cristispira", "cristiverpa", "cristobal", "cristobala", "cristobalensis", "cristobalia", "cristoides", "cristonothrus", "cristophylla", "cristovalensis", "cristovaoi", "cristula", "cristulata", "cristulatum", "cristulatus", "cristuliflora", "cristulifrons", "cristulipes", "cristulum", "cristus", "crisulipora", "critchleyi", "critesion", "crithagra", "crithionina", "crithmifolia", "crithmoides", "critho", "crithodium", "crithopyrum", "critica", "criticum", "criticus", "critola", "critolaus", "critomolgus", "criton", "critonia", "crittersius", "crius", "crivellarii", "crnobog", "crnri", "croasdaleae", "croatanensis", "croatania", "croatanica", "croatica", "croaticum", "croaticus", "croatii", "crobylophorus", "crobylura", "crocaceae", "crocale", "crocallata", "crocallis", "crocana", "crocanthemum", "crocata", "crocatum", "crocatus", "crocea", "croceareolata", "crocearia", "croceata", "croceater", "croceator", "croceatus", "croceguttatus", "croceibacter", "croceicauda", "croceicincta", "croceicoccus", "croceicollis", "croceicornis", "croceiflorus", "croceipennis", "croceipes", "croceitalea", "croceitarsis", "croceithorax", "croceiventre", "croceiventris", "croceoida", "croceoides", "croceoinguinis", "croceola", "croceolanata", "croceomaculatus", "croceopodes", "croceosignatus", "croceovittata", "croceovittatus", "croces", "croceum", "croceus", "croci", "crociaeus", "crocias", "crocidema", "crocidium", "crocidolomiae", "crocidopoma", "crocidura", "crocidurae", "crocidurai", "crocidurinae", "crociduroides", "crocidurus", "crocifera", "crocigrapha", "crocina", "crocinae", "crocineus", "crocinitomix", "crocinopterus", "crocinosoma", "crocinubia", "crocinum", "crocinus", "crocisa", "crocisaeformis", "crockerella", "crockeri", "crockeria", "crockeriana", "crockerinus", "crockettorum", "crococephala", "crocodila", "crocodilensis", "crocodili", "crocodilia", "crocodilichthys", "crocodilinus", "crocodill", "crocodillicola", "crocodilorum", "crocodilosa", "crocodilurus", "crocodilus", "crocodyli", "crocodylia", "crocodylidae", "crocodylus", "crocogaster", "crocolita", "croconota", "croconotus", "crocopeplus", "crocopygia", "crocopygius", "crocorrhoa", "crocosema", "crocosmia", "crocosmiiflora", "crocostethus", "crocota", "crocothemis", "crocotia", "crocotila", "crocoturum", "crocotus", "crocro", "crocus", "crocusella", "crocuta", "crocutasis", "crocutella", "crocynia", "crocyniaceae", "croeciclava", "croeseri", "croesia", "croesioides", "croesus", "croftia", "croftiae", "croftii", "croftoni", "croftus", "crogmaniana", "croicensis", "croilia", "croisseti", "croix", "croizati", "croizatii", "crokeri", "cromagnonensis", "crombiei", "crombota", "cromeria", "cromerus", "cromileptes", "cromion", "cromis", "cromwellii", "cromyorhizon", "cronadun", "cronartiaceae", "cronartium", "cronebergi", "cronebergii", "croni"]
Promise .resolve (words)
.then (process)
.then (breakdowns => breakdowns .map (({p, i, s}) => `${p ? `(${p}-)` : ''}(${i})${s ? `(-${s})` : ''}`))
.then (words => console .log (words .join ('\n')))
.as-console-wrapper {max-height: 100% !important; top: 0}
我用来显示这些的格式与建议的格式略有不同，因为我想允许没有前缀或没有后缀的版本，但仍然非常可读和明确。因此 (crist-)(atellid)(-ae) 应该很清楚了。这三个部分中的每一个都被括号括起来。前缀以连字符结尾，后缀以一开头。这是输出文件中的格式，但更改它是微不足道的——只需调整最后一个块中提供给 breakdowns .map () 的函数即可。
一个有趣的问题，我希望下周能抽出时间仔细研究一下。
词缀可以是前缀（词前）、中缀（词中）或后缀（词后）。我有一个 list of 200k+ latin/greek names used in biological taxonomy. It turns out there is no centralized list of all the affixes used in the taxonomy, unfortunately, other than this very basic list.
问题是，我怎样才能将 200k+ 的 latin/greek 名称列表分成词缀列表（最好只使用普通的 JavaScript）？
我真的不知道从哪里开始。如果我构造一个 trie，我需要以某种方式测试特定的词块。或者，如果可以扩展该块，则在我们达到某种最终扩展之前不要包含该块...
const fs = require('fs')
const words = fs.readFileSync(`/Users/lancepollard/Downloads/all.csv`, 'utf-8').trim().split(/\n+/)
const trie = { children: {} }
words.forEach(word => addToTrie(trie, word))
function addToTrie(trie, word) {
let letters = word.trim().split('')
let node = trie
let i = 0
while (i < letters.length) {
let letter = letters[i++]
node = node.children[letter] = node.children[letter] || { children: {} }
}
node.isWord = true
}
它不需要精确，就像每个词缀实际上都意味着什么，它可能是脏的（在那种情况下，有些词有某种意义，有些词没有）。但它不应该只列出单词字母的每一种排列之类的东西。它应该包括“潜在词缀候选”的东西，它们是在列表中出现不止一次的块。这至少会让我到达那里，然后我可以手动浏览并查找每个“块”的定义。理想情况下，它还应该指出它是否是 prefix/infix/suffix。也许输出是 CSV 格式 affix,position.
您可以在如何解决这个问题上发挥创意，因为如果事先不知道可能的词缀列表，我们就不知道确切的输出应该是什么。这基本上是尝试 找到 尽可能最好的词缀。例如，如果它包含像 aa- 这样的前缀，这可能是一个常见的字母序列，但我认为它不是词缀，这对我来说很好，它可以手动过滤掉。但是如果有两个词（我编的），比如 abrogati 和 abrowendi，那么 abro 将是一个“公共前缀”，并且应该包含在最终列表中，而不是 abr、ab 和 a，尽管它们也很常见。基本上，最长的公共前缀。然而，如果我们有单词 apistal 和 ariavi，我们可以说 a 是一个公共前缀，所以我们的最终列表将包括 a 和 abro .
更详细一点，假设我们有这两个词 aprineyanilantli 和 aboneyanomantli，它们有共同的前缀 a- 和共同的后缀 -antli ，以及中缀 -neyan-，因此它们应该在最终列表中。
它不一定需要高效，因为理论上这只会 运行 一次，在 200k+ 列表上。但如果它也有效率，那将是额外的好处。理想情况下，运行 应该不需要几个小时，但我不确定什么是可能的:)
另一个例子是这样的：
brevidentata
brevidentatum
brevidentatus
crassidentata
crassidentatum
crassidentatus
这里，前3个有共同的前缀，brevidentat，然后2-3有共同的前缀brevidentatu。但后来（根据人类知识），我们发现 identat 可能是我们想要的 infix，而 a/um/us是单词形式的后缀。另外，我们看到 identat 是 crass... 和 brev... 这两个词的中缀。所以最终结果应该是：
brav-
crass-
-identat-
-a
-us
-um
从理论上讲，这将是理想的结果。但你也可以这样：
brav-
crass-
-identat-
-identata
-identatus
-identatum
这也行，我们可以做一些简单的过滤，稍后再过滤掉。
注意，我不关心 环绕 其他东西的单词部分意义上的中缀，比如 stufffoo...barstuff，其中 foo...bar 包裹了一些东西。我只关心重复的单词部分，比如前缀、后缀、单词中间的东西。
这里有一个简单的方法，不过大概是在小时内。此外，您可以在 JavaScript 中执行此操作，但我将采用通用的 Unixy 方法，您可以用任何语言编写该方法，因为这很容易考虑。
首先，让我们获取您的文件，并在每个单词的 start/end 和字母之间的 space 处添加标记。所以你的例子会变成：
^ b r e v i d e n t a t a $
^ b r e v i d e n t a t u m $
^ b r e v i d e n t a t u s $
^ c r a s s i d e n t a t a $
^ c r a s s i d e n t a t u m $
^ c r a s s i d e n t a t u s $
这是我们的一般表示，space 分隔可能的词缀。基本词缀是字母、开始和结束。当然，这里我们没有找到词缀。
这是单个词缀搜索过程的样子。
拿我们的文件，创建 tempfile 个不同的可能词缀部分，然后是单词的行号。 （我说 distinct 这样如果行 666 包含 a b a b 你就不会得到 a b: 666 两次。）所以我们的文件开始于：
^ b: 1
^ b r: 1
.
.
.
^ c r a s s i d e n t a t u s $: 6
接下来我们 sort 文件（只需使用 Unix LC_ALL=C sort tempfile > sortedtempfile 命令，LC_ALL 强制进行 asciibetical 排序）。您现在生成 sortedtempfile 开始于：
^ b: 1
^ b: 2
.
.
.
^ c r a s s i d e n t a t u s $: 6
下一个 运行 一个自定义命令，为每个至少出现 2 次的前缀指定您将其用作词缀保存的符号数，然后是词缀，然后是列表它出现的地方。这会生成一个文件 tempsaved，开始于：
3: ^ b: 1 2 3
6: ^ b r e: 1 2 3
.
.
.
16: v i d e n t a t u: 2 3
现在执行 sorted -rn tempsaved > sortedtempsaved 从最大节省排序，首先找到最大节省。此文件现在开始
36: ^ c r a s s i d e n t a t: 4 5 6
33: ^ b r e v i d e n t a t: 1 2 3
36: ^ c r a s s i d e n t a: 4 5 6
在下一个函数中，我们识别词缀，直到在同一行号上遇到 2 个词缀。然后返回到我们的原始文件并应用它们。因此，在此遍中，我们将确定 ^crassidentat 和 ^brevidentat。然后生成一个新文件，其中包含：
^brevidentat a $
^brevidentat u m $
^brevidentat u s $
^crassidentat a $
^crassidentat u m $
^crassidentat u s $
现在重复。
在您的示例中，您将得到以下一组词缀：
^crassidentat
^brevidentat
um$
us$
a$
如果您将单词 identata、identatum 和 identatus 添加到原始列表，相同的算法将生成以下词缀列表
identat
^crass
^brev
um$
us$
a$
这是你所说的理想结果。
我的信封背面说您应该预计每次通过需要几分钟时间。但是我们试图在每次通过时找到很多词缀。所以我预计这不会超过几十次。此外，该列表之后还需要人工审核。我认为没有什么可以避免的。
前缀和后缀使用 Trie 很容易。但是，Trie 不会帮助您处理中缀。
Trie 示例代码（在 Java 中，未经测试，不完整）
class Node {
private int cnt;
private Map<Character, Node> children;
Node() {
cnt = 0;
this.children = new HashMap<>();
}
Node(String s, int pos) {
this();
addChild(s, pos);
}
bool isLeaf() {
return this.children.size() == 0
}
void addChild(String s, int pos) {
if (pos == s.length()) {
return;
}
char c = s.charAt(pos);
if (children.containsKey(c)) {
children.get(c).addChild(s, pos + 1);
} else {
children.put(c, new Node(s, pos + 1));
}
cnt++;
}
void removeChild(char c) {
int ccnt = 0;
Node child = children.remove(c);
if (child != null) {
ccnt = child.cnt;
}
cnt -= ccnt;
}
// other methods as necessary for traversal/value lookup...
}
class Solution {
private Node preroot = new Node();
private Node sufroot = new Node();
void addWord(String s) {
preroot.addChild(s, 0);
sufroot.addChild(new StringBuilder(s).reverse().toString(), 0);
}
void findPrefixes(int minOccur) {
// standard tree traversal on preroot,
// starting at the left-most leaf.
// when it finds a non-leaf with cnt >= minOccur
// output all permutations and remove the child.
}
}
中缀
中缀的问题是你不知道从哪里开始。 即采用字符串 abcdefgh 和 pppbcdefgzzzz，它们具有共同的中缀 bcdefg。此外，abcdefgh 和 pppabcdefgzzz 怎么样？
要解决这个问题，您基本上需要将单词分解成所有可能的成分，然后指向单词。 然后遍历印章列表，按长度降序排序，并删除与“使用过”的单词相关的所有条目。
即abc 将成为查找条目：abc、ab、bc、a、b、c。 然后查找 table 看起来像：
单词与符号的关联：
{abc -> {abc, ab, bc, a, b, c}}
地图：
{abc -> { abc }}
{ab -> { abc }}
{bc -> { abc }}
{a -> { abc }}
{b -> { abc }}
{c -> { abc }}
当我们添加 bcd 时，它会添加符号：bcd、bc、cd、b、c、d，添加单词关联并更新查找 table：
{abc -> { abc }}
{bcd -> { bcd }}
{ab -> { abc }}
{bc -> { abc, bcd }}
{cd -> { bcd }}
{a -> { abc }}
{b -> { abc, bcd }}
{c -> { abc, bcd }}
{d -> { bcd }
然后使用映射键的长度来指定排序顺序。从顶部开始，导航直到达到最少出现次数，然后使用该列表中的单词并从结构中删除单词。从映射中删除单词使用之前保存的单词关联来查找符号映射中的键。
这是一个有趣的问题，我有一个解决方案的草图，其中包含 运行 可用的代码和一些合理的——但远非完美的——输出。使用变体即使不是很快，也很容易。
想法是首先 运行 遍历所有单词，以各种可能的方式拆分它们，然后计算所有单词中每个前缀、中缀和后缀的出现次数，最后使用它信息以及评分函数，以选择每个单词的最佳表示。
我测试过的评分函数涉及前缀长度、该前缀在所有单词中的计数以及后缀和词缀的相同因素的组合。一般来说，我对长度的权衡远大于对数量的权衡，现在我主要关注前缀，只稍微权衡后缀。
运行 这需要几分钟，但比 Node 默认获得的内存多。我运行它作为
node --max-old-space-size=8192 index
这似乎就足够了。我还没有用 4GB 试过。
我的代码看起来像这样，最近的（也是我最喜欢的）评分函数：
const {readFile, writeFile} = require ('fs') .promises
const range = (lo, hi) =>
Array .from ({length: hi - lo}, (_, i) => i + lo)
const chooseTwo = (n) =>
range (0, n) .flatMap (i => range (i + 1, n + 1) .map (j => [i, j]))
const maximumBy = (fn) => (xs) =>
xs .reduce ((max, x) => {
const xScore = fn (x);
return xScore > max .score ? {score: xScore, val: x} : max;
}, {score: -Infinity}) .val
const breakdown = (word) => {
const len = word.length;
const ranges = chooseTwo (len);
return [
... ranges .map (([i, j]) => ({p: word .slice (0, i), i: word .slice (i, j), s: word .slice (j)})),
... range (0, len - 1) .map (i => ({p: '', i: word .slice (0, i), s: word .slice (i)})),
];
}
const score = (counts) => ({p, i, s}) =>
Math .max (1, Math .sqrt (1 + counts .prefixes [p]) * p .length ** 2) *
// Math .max (1, counts .infixes [i] * i .length ) *
Math .max (1, counts .suffixes [s] * s .length)
const process = (words) => {
const breakdowns = words .map (breakdown)
const counts = breakdowns .reduce (
(all, breakdown) => breakdown .reduce (
(all, {p, i, s}) => {
all .prefixes [p] = (all .prefixes [p] || 0) + 1;
all .infixes [i] = (all .infixes [i] || 0) + 1;
all .suffixes [s] = (all .suffixes [s] || 0) + 1;
return all;
},
all
),
{prefixes: {}, infixes: {}, suffixes: {}}
)
return breakdowns .map (maximumBy (score (counts)))
}
readFile ('./all.csv', 'utf8')
.then (s => s.split ('\n'))
.then (process)
.then (breakdowns => breakdowns .map (({p, i, s}) => `${p ? `(${p}-)` : ''}(${i})${s ? `(-${s})` : ''}`))
.then (words => writeFile ('./res.csv', words .join ('\n')), 'utf8')
.then (() => console .log ('Result written'))
第一个重要的函数是breakdown，例如，将'horse'变成：
(h)(-orse)
(ho)(-rse)
(hor)(-se)
(hors)(-e)
(horse)
(h-)(o)(-rse)
(h-)(or)(-se)
(h-)(ors)(-e)
(h-)(orse)
(ho-)(r)(-se)
(ho-)(rs)(-e)
(ho-)(rse)
(hor-)(s)(-e)
(hor-)(se)
(hors-)(e)
()(-horse)
(h)(-orse)
(ho)(-rse)
(hor)(-se)
(h-)(orse)
(ho-)(rse)
(hor-)(se)
(hors-)(e)
与 p、i 和 s 属性在内部存储，用于 prefix、infix 和 suffix，所以它实际上看起来像这样：
[
{p: '', i: 'h', s: 'orse'},
{p: '', i: 'ho', s: 'rse'},
{p: '', i: 'hor', s: 'se'},
{p: '', i: 'hors', s: 'e'},
{p: '', i: 'horse', s: ''},
{p: 'h', i: 'o', s: 'rse'},
{p: 'h', i: 'or', s: 'se'},
{p: 'h', i: 'ors', s: 'e'},
{p: 'h', i: 'orse', s: ''},
{p: 'ho', i: 'r', s: 'se'},
{p: 'ho', i: 'rs', s: 'e'},
{p: 'ho', i: 'rse', s: ''},
{p: 'hor', i: 's', s: 'e'},
{p: 'hor', i: 'se', s: ''},
{p: 'hors', i: 'e', s: ''},
{p: '', i: '', s: 'horse'},
{p: '', i: 'h', s: 'orse'},
{p: '', i: 'ho', s: 'rse'},
{p: '', i: 'hor', s: 'se'},
{p: 'h', i: 'orse', s: ''},
{p: 'ho', i: 'rse', s: ''},
{p: 'hor', i: 'se', s: ''},
{p: 'hors', i: 'e', s: ''},
]
breakdown 建立在两个简单的函数上：range 创建一个整数范围，开始时包含在内，结束时不包含，因此 range (3, 12) 产生 [3, 4, 5, 6, 7, 8, 9, 10, 11] . chooseTwo 找到 0 和 n 之间的所有不同整数对。
我们的第二个主要功能是 process，它使用 breakdown 和 maximumBy 执行上述算法，我们使用 [=34= 选择最大值细分] 功能。在这两者之间，我们简单地计算使用的零件。
这就是所有基础设施。重要工作在 score。您可以通过多种方式更改它。如果不是假期时间，我很想尝试一下这个的变体。但是，当您这样做时，您应该注意，尽管使用一小部分数据很容易获得看起来合理的结果，但对于完整数据而言，这并不总是如此合理。因此，您将需要 运行 具有各种功能的完整代码。
我建议调查的一件事是是否有一个相当准确的英语预测断字工具——不是基于字典的，而是合理的第一原则或一些机器学习的结果 运行s。一个好的断字决定可能会帮助您编写更好的评分函数。
如果您想在一小部分数据中看到这一点，您可以扩展以下代码段：
const range = (lo, hi) =>
Array .from ({length: hi - lo}, (_, i) => i + lo)
const chooseTwo = (n) =>
range (0, n) .flatMap (i => range (i + 1, n + 1) .map (j => [i, j]))
const maximumBy = (fn) => (xs) =>
xs .reduce ((max, x) => {
const xScore = fn (x);
return xScore > max .score ? {score: xScore, val: x} : max;
}, {score: -Infinity}) .val
const breakdown = (word) => {
const len = word.length;
const ranges = chooseTwo (len);
return [
... ranges .map (([i, j]) => ({p: word .slice (0, i), i: word .slice (i, j), s: word .slice (j)})),
... range (0, len - 1) .map (i => ({p: '', i: word .slice (0, i), s: word .slice (i)})),
];
}
const score = (counts) => ({p, i, s}) =>
Math .max (1, Math .sqrt (1 + counts .prefixes [p]) * p .length ** 2) *
// Math .max (1, counts .infixes [i] * i .length ) *
Math .max (1, counts .suffixes [s] * s .length)
const process = (words) => {
const breakdowns = words .map (breakdown)
const counts = breakdowns .reduce (
(all, breakdown) => breakdown .reduce (
(all, {p, i, s}) => {
all .prefixes [p] = (all .prefixes [p] || 0) + 1;
all .infixes [i] = (all .infixes [i] || 0) + 1;
all .suffixes [s] = (all .suffixes [s] || 0) + 1;
return all;
},
all
),
{prefixes: {}, infixes: {}, suffixes: {}}
)
return breakdowns .map (maximumBy (score (counts)))
}
const words = ["cristata", "cristatella", "cristatellidae", "cristatellus", "cristaticeps", "cristaticollis", "cristatiforme", "cristatifrons", "cristatigena", "cristatipes", "cristatispinosa", "cristatissimus", "cristatogobius", "cristatoides", "cristatolabra", "cristatopalpus", "cristatula", "cristatum", "cristatus", "cristavarius", "cristellaria", "cristeremaeus", "cristi", "cristianalemani", "cristiani", "cristibrachium", "cristicauda", "cristiceps", "cristicola", "cristicollis", "cristidigitus", "cristifer", "cristifera", "cristiferus", "cristiformis", "cristifrons", "cristigera", "cristiglans", "cristiloba", "cristimanus", "cristina", "cristinae", "cristipalpis", "cristipes", "cristirhizophorum", "cristis", "cristispira", "cristiverpa", "cristobal", "cristobala", "cristobalensis", "cristobalia", "cristoides", "cristonothrus", "cristophylla", "cristovalensis", "cristovaoi", "cristula", "cristulata", "cristulatum", "cristulatus", "cristuliflora", "cristulifrons", "cristulipes", "cristulum", "cristus", "crisulipora", "critchleyi", "critesion", "crithagra", "crithionina", "crithmifolia", "crithmoides", "critho", "crithodium", "crithopyrum", "critica", "criticum", "criticus", "critola", "critolaus", "critomolgus", "criton", "critonia", "crittersius", "crius", "crivellarii", "crnobog", "crnri", "croasdaleae", "croatanensis", "croatania", "croatanica", "croatica", "croaticum", "croaticus", "croatii", "crobylophorus", "crobylura", "crocaceae", "crocale", "crocallata", "crocallis", "crocana", "crocanthemum", "crocata", "crocatum", "crocatus", "crocea", "croceareolata", "crocearia", "croceata", "croceater", "croceator", "croceatus", "croceguttatus", "croceibacter", "croceicauda", "croceicincta", "croceicoccus", "croceicollis", "croceicornis", "croceiflorus", "croceipennis", "croceipes", "croceitalea", "croceitarsis", "croceithorax", "croceiventre", "croceiventris", "croceoida", "croceoides", "croceoinguinis", "croceola", "croceolanata", "croceomaculatus", "croceopodes", "croceosignatus", "croceovittata", "croceovittatus", "croces", "croceum", "croceus", "croci", "crociaeus", "crocias", "crocidema", "crocidium", "crocidolomiae", "crocidopoma", "crocidura", "crocidurae", "crocidurai", "crocidurinae", "crociduroides", "crocidurus", "crocifera", "crocigrapha", "crocina", "crocinae", "crocineus", "crocinitomix", "crocinopterus", "crocinosoma", "crocinubia", "crocinum", "crocinus", "crocisa", "crocisaeformis", "crockerella", "crockeri", "crockeria", "crockeriana", "crockerinus", "crockettorum", "crococephala", "crocodila", "crocodilensis", "crocodili", "crocodilia", "crocodilichthys", "crocodilinus", "crocodill", "crocodillicola", "crocodilorum", "crocodilosa", "crocodilurus", "crocodilus", "crocodyli", "crocodylia", "crocodylidae", "crocodylus", "crocogaster", "crocolita", "croconota", "croconotus", "crocopeplus", "crocopygia", "crocopygius", "crocorrhoa", "crocosema", "crocosmia", "crocosmiiflora", "crocostethus", "crocota", "crocothemis", "crocotia", "crocotila", "crocoturum", "crocotus", "crocro", "crocus", "crocusella", "crocuta", "crocutasis", "crocutella", "crocynia", "crocyniaceae", "croeciclava", "croeseri", "croesia", "croesioides", "croesus", "croftia", "croftiae", "croftii", "croftoni", "croftus", "crogmaniana", "croicensis", "croilia", "croisseti", "croix", "croizati", "croizatii", "crokeri", "cromagnonensis", "crombiei", "crombota", "cromeria", "cromerus", "cromileptes", "cromion", "cromis", "cromwellii", "cromyorhizon", "cronadun", "cronartiaceae", "cronartium", "cronebergi", "cronebergii", "croni"]
Promise .resolve (words)
.then (process)
.then (breakdowns => breakdowns .map (({p, i, s}) => `${p ? `(${p}-)` : ''}(${i})${s ? `(-${s})` : ''}`))
.then (words => console .log (words .join ('\n')))
.as-console-wrapper {max-height: 100% !important; top: 0}
我用来显示这些的格式与建议的格式略有不同，因为我想允许没有前缀或没有后缀的版本，但仍然非常可读和明确。因此 (crist-)(atellid)(-ae) 应该很清楚了。这三个部分中的每一个都被括号括起来。前缀以连字符结尾，后缀以一开头。这是输出文件中的格式，但更改它是微不足道的——只需调整最后一个块中提供给 breakdowns .map () 的函数即可。
一个有趣的问题，我希望下周能抽出时间仔细研究一下。