精华内容
下载资源
问答
  • python 字典生成树状图

    千次阅读 2019-11-11 09:19:08
    from graphviz import Digraph # 获取所有节点中最多子节点的叶节点 def getMaxLeafs(myTree): numLeaf = len(myTree.keys()) for key, value in myTree.items(): if isinstance(value, dict): ...
    from graphviz import Digraph
    
    
    # 获取所有节点中最多子节点的叶节点
    def getMaxLeafs(myTree):
        numLeaf = len(myTree.keys())
        for key, value in myTree.items():
            if isinstance(value, dict):
                sum_numLeaf = getMaxLeafs(value)
                if sum_numLeaf > numLeaf:
                    numLeaf = sum_numLeaf
        return numLeaf
    
    
    def plot_model(tree, name):
        g = Digraph("G", filename=name, format='png', strict=False)
        first_label = list(tree.keys())[0]
        g.node("0", first_label)
        _sub_plot(g, tree, "0")
        leafs = str(getMaxLeafs(tree) // 10)
        g.attr(rankdir='LR', ranksep=leafs)
        g.view()
    
    
    root = "0"
    
    
    def _sub_plot(g, tree, inc):
        global root
    
        first_label = list(tree.keys())[0]
        ts = tree[first_label]
        for i in ts.keys():
            if isinstance(tree[first_label][i], dict):
                root = str(int(root) + 1)
                g.node(root, list(tree[first_label][i].keys())[0])
                g.edge(inc, root, str(i))
                _sub_plot(g, tree[first_label][i], root)
            else:
                root = str(int(root) + 1)
                g.node(root, tree[first_label][i])
                g.edge(inc, root, str(i))
    
    
    tree = {
            "tearRate": {
                "reduced": "no lenses",
                "normal": {
                    "astigmatic": {
                        "yes": {
                            "prescript": {
                                "myope": "hard",
                                "hyper": {
                                    "age": {
                                        "young": "hard",
                                        "presbyopic": "no lenses",
                                        "pre": "no lenses"
                                    }
                                }
                            }
                        },
                        "no": {
                            "age": {
                                "young": "soft",
                                "presbyopic": {
                                    "prescript": {
                                        "myope": "no lenses",
                                        "hyper": "soft"
                                    }
                                },
                                "pre": "soft"
                            }
                        }
                    }
                }
            }
        }
    plot_model(tree, "tree.gv")
    

    效果如下:
    在这里插入图片描述

    展开全文
  • Python实现字典树

    千次阅读 2018-08-28 17:11:31
    python实现字典树 前言 实现 附言 python实现字典树 前言  下文实现的字典树的目的其实并非用于存储字符,而是存储每个词语(虽然原理一致),并且支持获取某个词语序列的前后缀及其频率。当然,还缺少...

    python实现字典树

    前言

    下文实现的字典树的目的其实并非用于存储字符,而是存储每个词语(虽然原理一致),并且支持获取某个词语序列的前后缀及其频率。当然,还缺少一些方法没写。(哎,主要是懒~~)

    实现

    直接上代码好了,有注释应该不是那么难以理解。结点的结构可以进行任意变更用以满足特殊需求。
      
      有一点不算是缺陷的缺陷,就是下文的search方法是用来查找完整句子的序列的,如果存在某个句子是其他句子的前缀,查询的时候将会返回false,这部分烦请根据实际情况进行修改。

    # -*- coding:utf-8 -*-
    """
    Description:大变双向字典树
    迭代次数默认最大999,可以增加但是没必要。其实能深到999层,那这个序列还是选择另外的处理方式吧。
    
    @author: WangLeAi
    @date: 2018/8/15
    """
    
    
    class TrieNode(object):
        def __init__(self, value=None, count=0, parent=None):
            # 值
            self.value = value
            # 频数统计
            self.count = count
            # 父结点
            self.parent = parent
            # 子节点,{value:TrieNode}
            self.children = {}
    
    
    class Trie(object):
        def __init__(self):
            # 创建空的根节点
            self.root = TrieNode()
    
        def insert(self, sequence):
            """
            基操,插入一个序列
            :param sequence: 列表
            :return:
            """
            cur_node = self.root
            for item in sequence:
                if item not in cur_node.children:
                    # 插入结点
                    child = TrieNode(value=item, count=1, parent=cur_node)
                    cur_node.children[item] = child
                    cur_node = child
                else:
                    # 更新结点
                    cur_node = cur_node.children[item]
                    cur_node.count += 1
    
        def search(self, sequence):
            """
            基操,查询是否存在完整序列
            :param sequence: 列表
            :return:
            """
            cur_node = self.root
            mark = True
            for item in sequence:
                if item not in cur_node.children:
                    mark = False
                    break
                else:
                    cur_node = cur_node.children[item]
            # 如果还有子结点,说明序列并非完整
            if cur_node.children:
                mark = False
            return mark
    
        def delete(self, sequence):
            """
            基操,删除序列,准确来说是减少计数
            :param sequence: 列表
            :return:
            """
            mark = False
            if self.search(sequence):
                mark = True
                cur_node = self.root
                for item in sequence:
                    cur_node.children[item].count -= 1
                    if cur_node.children[item].count == 0:
                        cur_node.children.pop(item)
                        break
                    else:
                        cur_node = cur_node.children[item]
            return mark
    
        def search_part(self, sequence, prefix, suffix, start_node=None):
            """
            递归查找子序列,返回前缀和后缀结点
            此处简化操作,仅返回一位前后缀的内容与频数
            :param sequence: 列表
            :param prefix: 前缀字典,初始传入空字典
            :param suffix: 后缀字典,初始传入空字典
            :param start_node: 起始结点,用于子树的查询
            :return:
            """
            if start_node:
                cur_node = start_node
                prefix_node = start_node.parent
            else:
                cur_node = self.root
                prefix_node = self.root
            mark = True
            # 必须从第一个结点开始对比
            for i in range(len(sequence)):
                if i == 0:
                    if sequence[i] != cur_node.value:
                        for child_node in cur_node.children.values():
                            self.search_part(sequence, prefix, suffix, child_node)
                        mark = False
                        break
                else:
                    if sequence[i] not in cur_node.children:
                        for child_node in cur_node.children.values():
                            self.search_part(sequence, prefix, suffix, child_node)
                        mark = False
                        break
                    else:
                        cur_node = cur_node.children[sequence[i]]
            if mark:
                if prefix_node.value:
                    # 前缀数量取序列词中最后一词的频数
                    if prefix_node.value in prefix:
                        prefix[prefix_node.value] += cur_node.count
                    else:
                        prefix[prefix_node.value] = cur_node.count
                for suffix_node in cur_node.children.values():
                    if suffix_node.value in suffix:
                        suffix[suffix_node.value] += suffix_node.count
                    else:
                        suffix[suffix_node.value] = suffix_node.count
                # 即使找到一部分还需继续查找子结点
                for child_node in cur_node.children.values():
                    self.search_part(sequence, prefix, suffix, child_node)
    
    
    if __name__ == "__main__":
        trie = Trie()
        texts = [["葬爱", "少年", "葬爱", "少年", "慕周力", "哈哈"], ["葬爱", "少年", "阿西吧"], ["烈", "烈", "风", "中"], ["忘记", "了", "爱"],
                 ["埋葬", "了", "爱"]]
        for text in texts:
            trie.insert(text)
        markx = trie.search(["忘记", "了", "爱"])
        print(markx)
        markx = trie.search(["忘记", "了"])
        print(markx)
        markx = trie.search(["忘记", "爱"])
        print(markx)
        markx = trie.delete(["葬爱", "少年", "王周力"])
        print(markx)
        prefixx = {}
        suffixx = {}
        trie.search_part(["葬爱", "少年"], prefixx, suffixx)
        print(prefixx)
        print(suffixx)
    

    附言

    好了,没其他什么特别的内容了。若有人问这个字典树有什么用呢?我的回答是目前用于存储词序列的数据结构,依赖这个结构可以进行词频统计、计算左右信息熵、计算点互信息等操作。

    展开全文
  • 主要介绍了Python实现简单字典的方法,实例分析了Python字典树的定义、实现与使用技巧,需要的朋友可以参考下
  • python实现字典树

    2018-08-09 16:19:28
    #定义一个字典树节点的类 class TrieNode(object): def __init__(self): """ Initialize your data structure here. """ self.data = {} self.is_word = False #字典树 class ...
    #定义一个字典树节点的类
    class TrieNode(object):
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.data = {}
            self.is_word = False
    
    #字典树
    class Trie(object):
    
        def __init__(self):
            self.root = TrieNode()
    
        def insert(self, word):
            """
            Inserts a word into the trie.
            :type word: str
            :rtype: void
            """
            node = self.root
            for letter in word:
                child = node.data.get(letter)
                if not child:
                    node.data[letter] = TrieNode()
                node = node.data[letter]
            node.is_word = True
    
        def search(self, word):
            """
            Returns if the word is in the trie.
            :type word: str
            :rtype: bool
            """
            node = self.root
            for letter in word:
                node = node.data.get(letter)
                if not node:
                    return False
            return node.is_word  # 判断单词是否是完整的存在在trie树中
    
        def starts_with(self, prefix):
            """
            Returns if there is any word in the trie
            that starts with the given prefix.
            :type prefix: str
            :rtype: bool
            """
            node = self.root
            for letter in prefix:
                node = node.data.get(letter)
                if not node:
                    return False
            return True
    
        def get_start(self, prefix):
            """
            Returns words started with prefix
            :param prefix:
            :return: words (list)
            """
            #利用到了递归
            def _get_key(pre, pre_node):
                words_list = []
                if pre_node.is_word:
                    words_list.append(pre)
                for x in pre_node.data.keys():
                    words_list.extend(_get_key(pre + str(x), pre_node.data.get(x)))
                return words_list
    
            words = []
            if not self.starts_with(prefix):
                return words
            # if self.search(prefix):
            #     words.append(prefix)
            #     return words
            node = self.root
            for letter in prefix:
                node = node.data.get(letter)
            return _get_key(prefix, node)
    
    
    # Your Trie object will be instantiated and called as such:
    trie = Trie()
    trie.insert("somestring")
    trie.insert("somebody")
    trie.insert("some")
    trie.insert("somebody1")
    trie.insert("somebody3")
    print(trie.search("key"))
    print(trie.search("somebody3"))
    print(trie.get_start('some'))

    æå¥æ°æ®åçç»æ

    ###########################################结果

    False
    True
    ['some', 'somestring', 'somebody', 'somebody1', 'somebody3']

    展开全文
  • python生成树结构

    2021-05-25 16:38:10
    # 生成树结构 def get_trees(data, key_column='elementId', parent_column='parentId', child_column='children'): """ :param data: 数据列表 :param key_column: 主键字段,默认id :param parent_column: ...
    # 生成树结构
    def get_trees(data,
                  key_column='elementId',
                  parent_column='parentId',
                  child_column='children'):
        """
        :param data: 数据列表
        :param key_column: 主键字段,默认id
        :param parent_column: 父ID字段名,父ID默认从0开始
        :param child_column: 子列表字典名称
        :return: 树结构
        """
        data_dic = {}
        for d in data:
            data_dic[d.get(key_column)] = d  # 以自己的权限主键为键,以新构建的字典为值,构造新的字典
    
        data_tree_list = []  # 整个数据大列表
        for d_id, d_dic in data_dic.items():
            pid = d_dic.get(parent_column)  # 取每一个字典中的父id
            if not pid:  # 父id=0,就直接加入数据大列表
                data_tree_list.append(d_dic)
            else:  # 父id>0 就加入父id队对应的那个的节点列表
                try:  # 判断异常代表有子节点,增加子节点列表=[]
                    data_dic[pid][child_column].append(d_dic)
                except KeyError:
                    data_dic[pid][child_column] = []
                    data_dic[pid][child_column].append(d_dic)
        return data_tree_list
    
    def recursion(data, l=None):
        if l is None:
            l = []
        for i in data:
            if 'children' in i:
                children=i.pop('children')
                l.append(i)
                recursion(children,l)
            else:
                l.append(i)
        return l

     

    展开全文
  • Python实现最小生成树--Prim算法和Kruskal算法

    千次阅读 热门讨论 2020-06-21 21:01:22
    Python实现最小生成树–Prim算法和Kruskal算法 文章目录Python实现最小生成树--Prim算法和Kruskal算法前言设计需求分析系统设计系统实现Prim算法Kruskal算法功能介绍测试数据及代码测试数据完整代码参考文章 前言 ...
  • python 生成目录

    2018-03-07 09:48:53
    正在学习Python,实现了一个生成目录的功能,练手小程序。可能代码写的不够好,会继续努力的,哪里写的不好的话,希望大家提出宝贵意见,共同学习。源码以及结果分享给大家# -*-encoding: utf-8 -*- ""&...
  • Python 递归查找字典树

    2020-11-26 23:11:10
    文章目录字典树1. 递归查找算法2. 测试结果 字典树 tree = {'WenLi': {'ShaoHu': {'ChuGan': {'YingHua': 'No', 'RuanNian': 'Yes'}}, 'QingXi': {'MiDu': {'Da': 'Yes', 'Xiao': 'No'}}, ...取生成树第一层属
  • 字典的嵌套在机器学习实战决策部分,生成决策时用到了字典的嵌套。>>>s1={'no surface':{}}>>>s1['no surfacce'][0]='no'>>>s1{'no surface':{0:'no'}}>>>s2={'flipper':{}}>>>s2['flipper'][0]='no'>>>s2['...
  • python 图 最小生成树

    千次阅读 2018-09-04 19:07:18
    # 对字典进行解包 for u, w in G[v].iteritems(): # hwapq优先级队列回自动弹出最小值,默认以元祖中第一个元素排序 # 所以第一个参数w代表权值,v,u表示两个顶点 heapq.heappush(edges, (w, v, u)) # 循环...
  • 调用方式 get_trees(Menu.objects.values().all()) # 生成树结构 def get_trees(data, key_column='id', parent_column='parent_id', child_column='children', current_column=None, current_path=None): """ :...
  • Python 字典

    2013-01-17 14:38:46
    前言: 话说前几天在segmentfault.com回答了个问题:怎样将包含元组的列表转换为字典?刚好这几天读了几篇关于Python dict的文章(可点击参考文献看),因此写篇小文做个笔记。本文不能算严格意义的原创,也算是...
  • file") for people,finger,file in walk_relation_tree(relation_tree): print(f"people_name:{people} | finger_name:{finger} | file_name:{file}") get_relation_tree()生成文件与路径的关系 { "001":{ "L1":[...
  • python字典与json互相转换

    千次阅读 2019-06-27 18:35:24
    python中,字典和json都是形结构,本身具有很强的相似性。但字典与json互相转换,还是需要一定方法的,这个方法就是调用json库(模块)。 1.字典转json 字典到JSON转化: jsoninfo = json.dumps(dict) # 输出...
  • 最小生成树即为图中权值最小的生成树生成树中所有边权重之和)。 例如对于无向图: 来说最小生成树就是: 1.1 最小生成树算法 最小生成树的算法主要有两个: Kruskal 算法 Prim 算法 1.1.1 Kruskal 算法 算法...
  • 最小生成树kruskal算法python实现

    千次阅读 2019-07-03 20:39:31
    #File Name : 最小生成树kruskal算法.py #思路 边权重从小到大排序 从权重小的边开始 #不形成回路就要,不然不要。直至包含所有点 #File Name : 并查集.py # 并查集结构 from heapq import * class Node(object): ...
  • 最小生成树之克鲁斯卡尔算法的python实现 克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同,它适合于求边稀疏的网的最小生成树。 算法思路 利用字典建立图 以字典的形式建立加权连通图,...
  • Python字典的嵌套操作

    千次阅读 2018-05-14 19:18:18
    在机器学习中会用字典的嵌套来存储决策的信息,对绘制形图有很大的作用,其中嵌套字典生成是一个递归的过程 如下所示: >>> s={'a':{0:'no',1:{'flippers':{0: 'no', 1: 'maybe'}}},...
  • 字典树建立(python

    2020-11-13 09:35:32
    比如Word2Vec的Huffman、K近邻的DKTree、频繁项集的FP字典Trie、高效的DAT字典树的建立 注意:跟trie并不完全相同 import pickle #保存类对象用 class root: def __init__(self): self.sub_nodes...
  • python实现决策树生成算法ID3、C4.5

    千次阅读 2019-04-25 15:37:46
    决策树生成算法python实现 前言: 本章节实现了ID3和C4.5的决策树生成算法,决策的剪枝请参考下一篇博客。算法是基于李航老师的《统计学习方法》,相关公式在代码中都分别标注了。博客内容参考于李航老师...
  • 思路分析Step1:用Prim算法生成最小生成树Step2:根据最小生成树中各边的权重及各点的度,从大到小对最小生成树进行剪枝操作,使各点的度为0或1。这个功能在程序中使用函数jianzhi实现的。Step3:将剪枝的结果连接...
  • #Editing time : 2019/7/3 20:40 #File Name : 最小生成树prim算法.py from heapq import * class Node(object): pass class UnionFindSet(object): def __init__(self,nodes): self.fatherDict = {} ...
  • 的遍历包括前序遍历(preorder),中序遍历(inorder)和后序遍历(postorder)。 前序遍历(preorder):在前序遍历中,先访问根节点,然后递归地前序遍历访问左子树,再递归地前序遍历访问右子。 中序遍历(inorder)...
  • 题目描述给定一个整数 n, 返回从 1 到 n 的字典顺序。例如,给定 n = 13,返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。题解排序法首先...
  • 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索得到最小生成树。最小生成树即在一个带权连通图中,不但包括了连通图里的所有顶点,且其所有边的权值之和亦为最小。 算法思路 利用字典建立图 以...
  • 字典Python语言中的一种数据结构,每一个字典元素是由一对key-value组成的。而字典的key和value分别以集合(Set)形似组织,以便快速查询。集合的存储形似通常是的结构,所以搜索非常快。我们可以单独通过字典的...
  • 图的基本概念: ... 最小生成树(MST:minimum spanning tree):边权之和最小的树,n个顶点产生(n-1)个边 Kruskal算法原理: 将边按权重从小到大进行排序; 将每个顶点独立视为根节点,产生n个树; ...
  • 哈夫曼/赫夫曼 Python实现赫夫曼 Python实现哈夫曼 哈夫曼编码 哈夫曼压缩 哈夫曼解压 最简单的方式实现哈夫曼

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,534
精华内容 6,213
关键字:

python字典生成树

python 订阅