哈夫曼树与哈夫曼编码器(python实现)

1.关于哈夫曼树

哈夫曼树基于加权二叉树,其基本要素包含左右子树、双亲、权重和编码。

class Node:
    def  __init__(self,right=None,left=None,parent=None,weight=0,charcode=None):
    self.right = right
    self.left = left
    self.parent = parent
    self.weight = weight
    self.charcode = charcode

2.哈弗曼算法

哈弗曼算法属于贪心法的一种,其基本思路是:编码以字符出现的频率作为权重,每次选权重最小的两个节点作为生成最优二叉树的左右孩子,并将权重之和作为根节点的权重,自底向上生成一颗带权路径长度最短的最优二叉树。

def sort(list):
    return sorted(list,key=lambda node:node.weight)

def Huffman(listOfNode):
    listOfNode = sort(listOfNode)
    while len(listOfNode) != 1:
        a,b = listOfNode[0],listOfNode[1]
        new = Node()
        new.weight, new.left, new.right = a.weight + b.weight, a, b
        a.parent, b.parent = new, new
        listOfNode.remove(a), listOfNode.remove(b)
        listOfNode.append(new)
        listOfNode = sort(listOfNode)
    return listOfNode

3.导入字符-权重文件(非算法思想部分)

为方便操作,将字符-权重字典保存为文本文件后,直接导入进行编码,使用Python文件曹组完成。

def inPutFile():
    global filename
    global listForEveryByte
    filename = raw_input("请输入要编码的文件(存放在源代码目录下):")
    global codeDict
    with open(filename,'rb') as f:
        data = f.read()
        for Byte in data:
            codeDict.setdefault(Byte,0) #每个字节出现的次数默认为0
            codeDict[Byte] += 1
            listForEveryByte.append(Byte)

def outputCompressedFile():
    global listForEveryByte
    fileString = ""
    with open(filename.split(".")[0]+".jbj","wb") as f:
        for Byte in listForEveryByte:
            fileString += encodeDict[Byte]  #构成一个长字符序列
        leng = len(fileString)
        more = 16-leng%16
        fileString = fileString+"0"*more          #空位用0补齐

        leng = len(fileString)
        i,j = 0,16
        while j <= leng:
            k = fileString[i:j]
            a = int(k,2)
            print(a)
            print(repr(struct.pack(">H",a)))
            f.write(struct.pack(">H",a))
            f.write(str(a))
            i=i+16
            j=j+16

4.编码

通过哈弗曼算法构造哈夫曼树后,编码过程为找到字符所在的叶子节点,以及从根节点到该叶子节点的路径,使用先序遍历的节点左树记为0,右树记为1,即可得到编码结果。

def encode(head,listOfNode):
    global encodeDict
    for e in listOfNode:
        ep = e
        encodeDict.setdefault(e.charcode,"")
        while ep != head:

            if ep.parent.left == ep:
                encodeDict[e.charcode] = "1"+encodeDict[e.charcode]
            else:
                encodeDict[e.charcode] = "0"+encodeDict[e.charcode]
            ep=ep.parent

5.执行算法与所得结果

if __name__ == '__main__':
    inPutFile()
    listOfNode = []
    for e in codeDict.keys():
        listOfNode.append(Node(weight=codeDict[e],charcode=e))
    head=Huffman(listOfNode)[0]
    encode(head,listOfNode)

    for i in encodeDict.keys():
        print(i,encodeDict[i])

大二小结

做完今天的电子设计,就是大二的结束了,感觉到时间的飞快,只剩下一年准备工作了。作为学渣一个我应该是不读研也考不上研的,不过潜意识一直认为,靠谱点的公司工作了三年的工程师技术绝对是吊打学校里读三年的研究生的,自然内心也对继续读书没有什么趋同感。虽然家里从上到下都要求让我读研,虽然无论他们还是我自己都不知道那种选择更好,不过近两年努力(挂了三科却学得了一点点技术,如果今年不重修完估计得延迟毕业了得)老爸不像之前那样觉得读研是必须的了,说能本科毕业就好。但即使如此也倍感压力之大,毕竟之前浪费了不少时间,现在得付出十二分的时间补一下技术,,按照目前进度觉得一年还是足够的还能留出来至少两个月上牛客准备刷下笔试题和面试题,看看剑指offer之类的,但愿学校大三不在有各种奇奇怪怪的事情就行(诸如这个假期近十天的课设+课设前假期让我不得不鸽掉本来准备的实习)。估计是既不擅长电子相关课程的原因,我内心对所有和电子直接相关的课程和老师都很排斥,以至于大学挂的三门课全部都是电子(数电、模电、通信原理)的,换句话说是极为讨厌硬件相关的。

我的大二时间线

2015 年9月:继续上一个项目,一个关于物流的网站开发。 2015 年10月:中南大学有色金属出版社网站开发。 2015 年11月:颓废的一个月,现在也想不起干了什么,学了什么。 2015 年12月:开始了解angular和node.js,准备走大前端,但学习遇上很多问题并且较难解决,中途暂时放弃。 2016 年1月:考试接近,复(yu)习(xi),第一次开始一天一本书,一夜一门课的玩命模式。 2016 年2月:回家,春节,购买了DO的国外服务器以免去备案的麻烦,搭建了博客准备记录以后,继续学了一段时间前端,重构了去 年的物流网站项目。 2016 年3月:返校,帮学长开发学校招聘网. 2016 年4月:补了《白色相簿2》,短短13集的动漫,却中毒颇深,后来玩了这款gal,此生无悔入白学。 2016 年5月:作为外包开发学校学生团队做的二手平台,据说后来他们拿了金奖并且基本拿下国赛,邀请我加入时候回绝了虽然知道拿下国赛意味着保研至少也是加分,但学校的那类比赛已经和我价值观冲突了许多。 2016 年6月:学了一段时间代码,月底考试,开始预习,一天一本书效果不错,基本全部过了。 2016 年7月:终于放假,准备过充电和学习为主的假期,间隔计划见高中同学。 总之这一年丧失诸多之前的热情,能力也变得平庸而没有大一的锐气,或者说我可能本来就是那种有想法没天赋和坚持的,很多本来能做好的被白白浪费,也没有勇气追求,或者说之前会的很多都是因为别人没有去学才能超越的,如果这样那下一年可能就会被更多人在技术上超越,所以必须重新继续了。

将项目从 GitHub 部署到服务器

原文转载自开源中国翻译,一大半是我翻译的。


GitHub以及它所依赖的版本控制系统Git,绝对是非常出色的项目管理和协作的工具,不管项目是不是跟代码相关。 本文会讨论有哪些选项可以让Git和Github更好的融入项目的工作流当中,以实现平滑的自动化的过程。 我把这些选项划分到不同的工具集当中,这些集合包括自动运行测试,以及拉取代码部署到服务器上等等。

为何要这样做?

有了这些自动化过程的运行,你和你的团队就可以只关注单纯的编码以及代码的合并,而不是每次build的时候都要花费几个小时去重复的做部署这样的事情。 自动化部署变化的主要问题是变化会自动地被部署。你必须信任你的团队以及他们写的代码。这就是为什么自动化部署和自动化测试的搭配成为典型,而下面提供的工具也反映了这一点。

Git Hooks(钩子)

Git内置了一套拓展框架叫做钩子(http://git-scm.com/book/en/v2/Customizing-Git-Git-Hooks)用来处理自动化部署,并且这些钩子一般在被特定的Git事件 ( certain points)触发后被调用在我们的第一端口用来处理任务。钩子可以被分为服务器端钩子与客户端钩子。 服务器端是用于监听网络操作的事件 ——比如,当存储库接收推送后。而客户端挂钩的触发是因为开发者进行了操作,如提交和合并。 这是在Git文档中hooks的完整列表(http://git-scm.com/book/en/v2/Customizing-Git-Git-Hooks)。 我会注释一对情侣在这里让你开始。希望这能让你在自己当前手动部署的项目工作流程中中变得非常有用。Hooks可以在任何语言的项目部署中运行,强大而灵活。

pre-commit

此这个钩子运行在其他所有钩子之前,并且在更改提交之前。可以用来在提交前检查代码错误。 我们在这里写一个JavaScript的小项目说明(当然,我故意留了你可以找到的bug)。 重命名hooks/pre-commit.sample 为 hooks/pre-commit,并进行如下测试命令,以这样的内容:

&lt;br&gt;
`#!/bin/shjshint index.js`&lt;br&gt;
试着提交这个变动:
`git commit -m &quot;adding Javascript 
你可以看到报错信息:&lt;br&gt;
`index.js: line 5, col 25, Missing semicolon.1 error`

添加缺少的分号后重新提交,不在报错。

post-receive

当推送远程Git仓库完成时,服务器端的该钩子触发。在这个例子中,我们推出一个简单的网站的最新版本到你的Web服务器目录,实际上是一个(最基本的)部署。 我有一个现有的网站包含有一个index.html页 - 以及我们在后面的例子将使用的其他网页。你也可以创建自己的,使用在这里设立仓库。 克隆仓库,通过指定–bear标记来创建一个只包含版本控制信息的存储库,而不是我们的代码仓库:

git clone --bare https://github.com/sitepoint-editors/GitHub-Auto-Deploy.git GitHu`&lt;br&gt;
现在我们添加钩子:
`cd GitHub-Auto-Deploy.git/hooksvi post-receive`
添加这些到文件中:&lt;
`git clone --bare https://github.com/sitepoint-editors/GitHub-Auto-Deploy.git GitHub-Auto-Deploy.git`&lt;
现在我们添加钩子:
`cd GitHub-Auto-Deploy.git/hooksvi post-receive`&lt;
添加这些到文件中:
`#!/bin/shgit --work-tree=/var/www/html --git-dir=/var/repo/GitHub-Auto-Deploy.git checkout -f`&lt;

注意:这些路径是基于Ubuntu环境下完成,所以记得要改变路径,以满足你的路径。 该命令将推出当前仓库到定义的工作目录,但没有任何版本控制数据。 更改文件属性使之可执行: chmod +x post-receive
小贴士:这些位置与Ubuntu的安装路径相关,所以一定记得要改变路径,以满足您的设置。该命令将检查当前的存储库到定义的工作目录,但没有任何版本控制数据。 将文件添加可执行的权限:
chmod +x post-receive
在你的本地端,像平时一样克隆这个库,使用你选择的工具,并添加一个新的远程的实时服务器(记得更改服务器的详细信息到你的Web服务器和用户的详细信息):
git remote add prod ssh://user@domain.com/var/repo/GitHub-Auto-Deploy.git
要部署到我们生产环境下的服务器来替代仓库,输入以下命令: git push prod master
你可以ls一下服务器的 var/www/html 目录,可以看到index.html文件已经被自动拷贝进你的web文件夹内啦。 如果你使用的是自己的Git仓库,你可以把它配置在同一台服务器上的应用,并实现自动化部署。如果你使用的是GitHub上或其他外部Git的服务,那么这个钩子还没有完全自动化,但它已经降到了一步。这可以进一步简化。 GitHub的post-receive 钩子中有一个可以使用reync或scp的选项。这是另外的一种选择——特别是当你的应用需要构建时(GitHub限制了可能的命令)——是使用post-receive 钩子来触发,然后使用-f选项可以检查出从GitHub的代码库的应用程序服务器上的脚本和运行其他一些必要的命令。这个时候,自动化部署开始变得复杂起来,我们不得不使用下一套工具来更好的完成。

从 GitHub 直接自动部署

GitHub 有它自己的文档来自动化部署到集成平台,这里包括一些托管提供商。 老实说,大部分文档都有些错误,不准确或者没有起到作用, 在一些主流的主机提供商那儿,我做了一些搜索链接到官方文档,对于其他一些提供商,我建议你使用 post-receiveor 持续集成的方法:
Heroku AWS Azure

持续集成(CI)服务

有许多无数的能够查看 GitHub 项目回购变更协议的应用服务,不仅能够为你部署,而且能够执行其他功能,诸如为你运行测试和构建过程。 一旦你移动到一个新的和更复杂的实例时,我们可以使用 CI 自动化构建项目过程。首先,拉伸一个存储库的 Master 分支,然后触发一个运行构建的 bash 脚本,并且部署流程以及对微博更新。CI 与 web 服务能够在同一台服务器上或者在不同的服务器上运行,这一切都取决于你的偏好。

Jenkins

你需要搭建你自己的 Jenkins 服务器,这意味着你可以完全地控制它,但必须要对它进行维护。幸运的是,它提供了多平台支持,如果你只是想要先简单尝试一下的话,这些支持也包括了 Docker。 Jenkins 使用插件实现了自己的大部分功能,并且由于其年代久远、开源的性质以及普及度很广,它拥有很多的插件。例如,有一些 Git、GitHub 和 Twitter 的相关插件。 Jenkins 需要大量的配置,而且有时,若想要将你需要的指令组合到一起来构造你所需的工作流程,可能需要大量的研究。

Travis

此外,在 GitHub 文档中,使用 GitHub 的 Travis 集成指令已经过时。现在,它更简单:阅读找出更多的 Travis 文档。 Travis 不需要任何主机与服务器设置,因此你无需投入太多的精力,就可以保持和试用CI,这是一个很好的起点。不过,扩展超出(综合)默认的集成将涉及到一些额外的配置工作。比如,微博请求对 webhooks 的访问。 在回购中,你会注意到 Travis– 特别是在配置自己的文件中,它有一个习惯,就是更新太慢。当你本身没有对 Travis 服务器进行访问时,那么这些问题就难以解决。

其他商业服务

持续集成已经日益流行了,所以已经有了非常多的新的服务和应用程序 – 很多是通过你可能已经在使用的工具的创作者释出的,并且将很和谐的融入到现有的工具链和工作流程当中。这里有些例子: https://buddy.works/ https://www.atlassian.com/software/bamboo/ https://www.jetbrains.com/teamcity/ https://codeship.com/ https://circleci.com/ https://saucelabs.com/ https://about.gitlab.com/gitlab-ci/ http://deploybot.com/


操作系统——处理器调度笔记

一、基本概念

1 作业:比程序更为广泛,不仅包含了通常的程序和数据,还包含了一份作业说明书,系统通过说明书对程序进行控制。 2 作业步:在作业运行期间,每个作业需要的顺序运行步骤。编译、连续装配、运行。 3 作业流:多个在内存存放的作业是输入作业刘;在操作系统控制,逐个进行处理的作业是处理作业流。 4 队列中的记录通常是进程的进程控制块 5 CPU的调度决策可在如下四种环境下发生 {a 当一个进程从运行状态切换到等待状态 b 当一个进程从运行状态切换到就绪状态 c 当一个进程从等待状态切换到就绪状态 d 当一个进程终止} 当调度只能发生在第一和第四种情况时,称调度方案是非抢占的,否则调度方案是可抢占的 采用非抢占调度,一旦CPU被分配给一个进程,那么该进程会一直使用CPU直到进程终止或切换到等待状态时释放CPU

二 调度准侧

1 CPU使用率:40 % 到90 % 2 吞吐量:一个单元时间内所完成进程的数量 3 周转时间:从进程提交到进程完成的时间间隔称为周转时间,周转时间是所有时间段之和,包括等待进入内存、在就绪队列中等待,在CPU上执行和I / O执行 4 等待时间:CPU调度算法并影响进程运行和执行I / O的时间量。只影响进程在就绪队列中等待所花费的时间 5 响应时间:从提交请求到产生第一响应的时间。是开始相应所需要的时间,而不是输出该响应所需要的时间 6 调度准则:对于系统,CPU使用率和吞吐量最大化,各类资源平衡利用;对于用户,周转时间、等待时间和相应时间最小,遵循优先权准则

三 CPU调度算法

1 先到先服务调度算法 FCFS 2 短作业有限调度算法 3 高优先权优先调度算法 每个进程都有一个优先权与其关联,具有最高优先权的进程会被最先分配到CPU资源,具有相同优先权的采用FCFS调度 优先权可以通过内部或外部方式来定义 优先权调度可以是抢占的或者非抢占的 优先权调度算法的一个主要问题是无穷阻塞。解决办法是老化,老化是一种技术,以逐渐增加在系统中等待很长时间的进程的优先权。 4 轮转法调度算法 专门为分时系统设计的,定义一个小时间单元,称为时间量或时间片。时间片通常为10ms到100ms。就绪队列作为循环队列处理。CPU调度程序循环就绪队列,为每个进程分配不超过一个时间片间隔的CPU。 如果上下文切换时间约为时间片的10 % ,那么约10 % 的CPU时间会浪费在上下文转换上。

一些链接

Nodex’s Hackers:

JustZht:天哥,iOS,也写unity,在中南最佩服的人,目前准备留美学习中

飞飞 : 大学好友,目前在中山大学读硕士做CV

neroyang:高中学弟,锋哥,全栈,C++/Java/PHP/js/Golang,天津大学毕业,目前是thoughtwork的高级工程师

nastul:中南大学好友,常见搞安卓和web,目前在墨尔本大学研究机器学习

gay平 :zpnaruto,腾讯前端,中南大学隔壁宿舍的好基友


CSU相关

joyseedog:权哥,今日头条iOS

zhangdongxuan:微信iOS

Tsukasa:也是白学家,华为云java

Equim:Eq酱,C#、node.js,大神学弟,女装大佬

AndyGu:豪哥,安卓开发


一些组织

中南大学苹果实验室:大三时候作为第一个程序员加入的学校实验室

关于我

Who am I ?

我是Bugzhang 95年出生 来自西北甘肃武威,目前在深圳工作 web全栈工程师 从事web开发接近2年 毕业于中南大学计算机系

What do I write ?

  • 生活点滴
  • 学习经验
  • 个人心得

所以大部分会是流水账式的烂文

What can I do ?

√=掌握技能 o=熟练技能 #=入门技能 - 计算机网络 √ - 操作系统 √ - 数据结构和算法 √ - 信息安全 √ - html/css/js √ - node.js √ - egg.js √ - vue √ - webpack √ - webkit √ - mysql √ - react √ - 编译原理 o - angular o - golang o - AE/final cut pro # - PS/Sketch #

How to contact me ?

评论:可以评论任意博客内容联系我: E-mail:nuptunee@gmail.com