以下是我在 node js 中的 Trie 实现。我正在加载一个在 Trie 中有大约 2.5L 行的文本文件。但是 trie 增长如此之快,以至于应用程序由于内存不足而崩溃。我正在加载的文件有键和值,我需要使用任何可能的平均值来找到特定对应键的值,但应该是最快的,因为我每小时要处理数百万条记录。
'use strict';
const config = require("../config/config");
const logger = config.appLogger;
const treemap = require("ts-treemap");
function newTrie() {
this.head = {
key : ''
, children: {}
}
}
newTrie.prototype.init = function(gts) {
var trieBckp = JSON.parse(JSON.stringify(this.head));
if (!gts) throw new Error("Invalid parameter [collection]");
try {
this.addAll(gts);
} catch (err) {
this.head = trieBckp;
throw err;
}
}
newTrie.prototype.addAll = function(gts){
for(let i=0; i < gts.length; i++){
this.addToTree(gts[i]);
}
}
newTrie.prototype.addToTree = function(obj){
logger.debug(`Object Add to Tree ${JSON.stringify(obj)}`);
let curNode = this.head;
let newNode = null;
let curChar = obj.KEY.slice(0,1);
let key = obj.KEY.slice(1);
while(typeof curNode.children[curChar] !== "undefined" && curChar.length > 0){
curNode = curNode.children[curChar];
curChar = key.slice(0,1);
key = key.slice(1);
}
while(curChar.length > 0) {
newNode = {
key : curChar,
value : key.length === 0 ? obj.GT : undefined,
children : {}
};
logger.debug(`New Node ${JSON.stringify(newNode)}`);
curNode.children[curChar] = newNode;
curNode = newNode;
curChar = key.slice(0,1);
key = key.slice(1);
}
logger.debug(`Trie after add ${JSON.stringify(this.head)}`);
}
newTrie.prototype.getTrie = function(key, mode) {
try {
let match = null;
if (!key) {
logger.error("Invalid parameter [key]");
return;
}
if (!mode) {
logger.error("Invalid parameter [mode]");
return;
}
if (key.length == 0) {
logger.error("getTrie parameter [key] is empty");
return;
}
if (this.head.size == 0) {
logger.error("getTrie trie is empty");
return;
}
if (mode == "bestMatch") {
var curNode = this.head
, curChar = key.slice(0,1)
, d = 0;
key = key.slice(1);
while(typeof curNode.children[curChar] !== "undefined" && curChar.length > 0){
curNode = curNode.children[curChar];
curChar = key.slice(0,1);
key = key.slice(1);
}
if (curNode.value != undefined && key.length === 0) {
match = curNode.value;
}
} else {
match = this.getTrie(key.slice(0,1));
}
if (match == null) {
logger.debug(`No match found for key ${key}`);
}
return match;
} catch (err) {
logger.error(`Error -${err}`);
throw err;
}
}
module.exports = newTrie;