时间戳

首页 > 解决方案 > 如何通过 C# 使用 trie 来避免内存不足

c# - 如何通过 C# 使用 trie 来避免内存不足

问题描述

如何将数十亿数据写入内存较少的 trie

我想从新闻中提取一些信息，例如公司名称，所以我将数十亿个公司名称写入 trie，但它需要大量内存并抛出内存不足异常，我不知道如何解决它，所以任何人都可以提供帮助，提前致谢。

    public class Node
    {
        public char Value { get; set; }

        public List<Node> Children { get; set; }

        public int Depth { get; set; }

        public string Code { get; set; }

        public bool Terminal { get; set; }

        public Node(char value, int depth)
        {
            Value = value;
            Depth = depth;
            Children = new List<Node>();
        }


        public Node FindChildNode(char c)
        {
            foreach (var child in Children)
                if (child.Value == c)
                    return child;

            return null;
        }


    }

    public class Trie
    {
        private  Node _root;

        public Trie()
        {
            _root = new Node('^',0);
        }

        public Node Prefix(string s)
        {
            var currentNode = _root;
            var result = currentNode;

            foreach (var c in s)
            {
                currentNode = currentNode.FindChildNode(c);
                if (currentNode == null)
                    break;
                result = currentNode;
            }

            return result;
        }



        public void Insert(string randomLength,string code)
        {
            var commonPrefix = Prefix(randomLength);
            var current = commonPrefix;

            for (var i = current.Depth; i < s.Length; i++)
            {
               var newNode = new Node(s[i], current.Depth + 1);
                if (i+1==s.Length)
                {
                    newNode.Terminal = true;
                    newNode.Code = code;
                }
                current.Children.Add(newNode);
                current = newNode;
            }

        }



    }

Trie t=新的 Trie();
t.Insert("C","ABCG00DFD"); 上面的语句运行了1000000000个循环，“C”可以替换为不同长度的不同字符串，随着循环的增加，它会抛出内存异常，那么如何避免或改变它呢？

标签： c#out-of-memorytrie

解决方案

试一试Trie，看看你是否可以让它满足你的需要：

public class Trie : Dictionary<char, Trie>
{
    public void Add(string value)
    {
        var c = String.IsNullOrEmpty(value) ? '\0' : value[0];
        if (!this.ContainsKey(c))
        {
            this[c] = new Trie();
        }
        if (c != '\0')
        {
            this[c].Add(value.Substring(1));
        }
    }
}

推荐阅读