該賞金過期5天。此問題的答案有資格獲得 500聲望獎勵。 Lance Pollard正在尋找規范的答案：
在 JavaScript 中尋找可以處理單詞中間的前綴、后綴和單詞部分的實作。
詞綴可以是前綴（詞前）、中綴（詞中間）或后綴（詞后）。我有一份生物分類學中使用的 20 萬多個拉丁/希臘名稱的串列。不幸的是，除了這個非常基本的串列之外，并沒有集中列出分類法中使用的所有詞綴。
問題是，我怎樣才能把那 20 萬多個拉丁/希臘名字的串列分成一個詞綴串列（最好只使用純 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
}
它不需要很精確，就像每個詞綴實際上都意味著什么，它可以是骯臟的（也就是說，有些詞意味著什么，有些詞沒有）。但它不應該只是列出單詞字母的每個排列之類的東西。它應該包括“潛在詞綴候選”的東西，它們是在串列中出現不止一次的塊。這至少會讓我走到一半，然后我可以手動查看并查找每個“塊”的定義。理想情況下，它還應該說明它是否是前綴/中綴/后綴。也許輸出是 CSV 格式affix,position。
您可以創造性地解決這個問題，因為如果事先不知道可能的詞綴串列，我們不知道確切的輸出應該是什么。這基本上是為了盡可能地找到詞綴。aa-例如，如果它包含前綴之類的東西，這可能是一個常見的字母序列，但我認為這不是詞綴，這對我來說很好，可以手動過濾掉。但是，如果有兩個詞（我在做這件事），說abrogati和abrowendi，那么abro將是一個“共同的前綴”，以及應包含在最終的名單，不abr，ab和a，即使這些是常見的了。基本上，最長的公共前綴。但是，如果我們有單詞apistal和ariavi，我們可以說這a是一個常見的前綴，所以我們的最終串列將包括a和abro。
更詳細一點，假設我們有這兩個詞aprineyanilantliand aboneyanomantli，它們有共同的前綴a-、共同的后綴-antli以及中綴-neyan-，所以它們應該在最終串列中。
它不一定需要高效，因為理論上這只會在 200k 串列上運行一次。但如果它也有效率，那將是獎勵。理想情況下，雖然它不應該需要幾個小時才能運行，但我不確定有什么可能:)
另一個例子是這樣的：
brevidentata
brevidentatum
brevidentatus
crassidentata
crassidentatum
crassidentatus
在這里，前 3 個有一個公共前綴, brevidentat，然后 2-3 個有公共前綴brevidentatu。但后來（與人類的知識），我們發現identat可能是綴我們的愿望，和a/ um/us是word格式的后綴。此外，我們看到這identat是兩個詞crass...和中的中綴brev...。所以最終的結果應該是：
brav-
crass-
-identat-
-a
-us
-um
從理論上講，這將是理想的結果。但你也可以有這個：
brav-
crass-
-identat-
-identata
-identatus
-identatum
這也可以，我們可以做一些簡單的過濾，以便稍后將它們過濾掉。
Note, I don't care about infixes in the sense of word parts that surround something else, like stufffoo...barstuff, where foo...bar wraps something. I just care about the word parts which are repeated, such as prefixes, suffixes, and stuff in the middle of words.
uj5u.com熱心網友回復：
這是一個簡單的方法，但可能是在幾個小時內。此外，您可以使用 JavaScript 來實作，但我將采用通用的 Unixy 方法，您可以使用任何語言撰寫它，因為這很容易考慮。
首先，讓我們獲取您的檔案，并在每個單詞的開頭/結尾添加標記，并在字母之間添加空格。所以你的例子會變成：
^ 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 $
這是我們的一般表示，空格分隔可能的詞綴。基本詞綴是字母、開始和結束。當然，我們在這里沒有發現詞綴。
這是單個詞綴搜索通道的樣子。
拿我們的檔案，創建tempfile不同的可能詞綴部分，然后是單詞的行號。（我說不同，這樣如果行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是檔案（只需使用 UnixLC_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$
如果將 words identata, identatumand添加identatus到原始串列中，則相同的演算法將生成以下詞綴串列
identat
^crass
^brev
um$
us$
a$
這是你所說的理想結果。
我的信封背面說你應該期望每次通過需要幾分鐘。但是我們試圖在每次通過時找到很多詞綴。所以我不希望這需要超過幾十遍。此外，該串列之后還需要人工審核。我認為沒有什么可以避免的。
uj5u.com熱心網友回復：
這是一個有趣的問題，我有一個解決方案的草圖，其中包含可運行的代碼和有點合理——但遠非完美——的輸出。玩變體很容易，如果不是很快的話。
這個想法是首先遍歷所有單詞，以各種可能的方式拆分它們，然后計算所有單詞中每個前綴、中綴和后綴的出現次數，最后使用該資訊以及評分函式，選擇每個單詞的最佳表示。
我測驗過的評分函式涉及前綴長度、所有單詞中該前綴的計數以及后綴和詞綴的相同因素的組合。一般來說，我對長度的權重比計數高得多，我現在關注前綴，只對后綴稍加權重。
運行這需要幾分鐘，但默認情況下比 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, val}, x, _, __, v = fn(x)) => v > max ? {max: v, val: x} : {max, val}, {max:-Infinity}) .val
const breakdown = (word, len = word.length, ranges = chooseTwo (len)) => [
... 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 (w => breakdown(w))
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屬性一起存盤在內部， for prefix, infix, and 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 is built on two trivial functions: range creates an integer range, inclusive on the start, exclusive on the end, so that range (3, 12) yields [3, 4, 5, 6, 7, 8, 9, 10, 11]. And chooseTwo finds all pairs of distinct integers between 0 and n.
Our second main function is process, which does the algorithm described above using breakdown and maximumBy, which we use to choose the maximum valued breakdown using the score function. In between, we simply count the parts used.
This is all infrastructure. The important work is in score. You can alter this in so many ways. If it wasn't holiday time, I would love to play around with variants of this. But when you do, you should note that although it's easy to play with a small subset of the data and get reasonable-looking results, that doesn't always scale so reasonable to the complete data. So you will need to run the full code with various functions.
One thing I would suggest investigating is whether there is a reasonably accurate predictive hyphenating tool for English -- not dictionary-based, but either the result of reasonable first principles or of some machine learning runs. A good hyphenation decision might help you write a better score function.
如果您想在一小部分資料中看到這一點，您可以展開以下代碼段：
顯示代碼片段
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, val}, x, _, __, v = fn(x)) => v > max ? {max: v, val: x} : {max, val}, {max:-Infinity}) .val
const breakdown = (word, len = word.length, ranges = chooseTwo (len)) => [
... 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 (w => breakdown(w))
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)應該就很清楚了。這三個部分中的每一個都用括號括起來。前綴以連字符結尾，后綴以 1 開頭。這是輸出檔案中的格式，但更改它是微不足道的——只需調整提供給breakdowns .map ()最后一個塊的函式即可。
一個引人入勝的問題，我希望下周有時間更仔細地研究它。
uj5u.com熱心網友回復：
前綴和后綴使用 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。然后查找表將如下所示：
單詞與符號的關聯：
{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，添加了單詞關聯并更新了查找表：
{abc -> { abc }}
{bcd -> { bcd }}
{ab -> { abc }}
{bc -> { abc, bcd }}
{cd -> { bcd }}
{a -> { abc }}
{b -> { abc, bcd }}
{c -> { abc, bcd }}
{d -> { bcd }
然后使用映射鍵的長度來指示排序順序。從頂部開始，導航直到達到最少出現次數，然后使用該串列中的單詞并從結構中洗掉這些單詞。從映射中洗掉單詞使用之前保存的單詞關聯來查找符號映射中的鍵。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/391948.html
上一篇：將vector<vector<string>>轉換為vector<vector<double>>的最佳方法是什么？
下一篇：Z80除法演算法運行不正常