0

以下是我在 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;
4

0 回答 0