Find all duplicates in two different arrays in LabVIEW, 200 times faster

Recently I have been learning Python, machine learning and Natural Language Processing (NLP). That’s why I didn’t post these days. In future posts, I hope I can share some interesting things in these subjects.

Yesterday I came across an algorithm that finds out all the same elements in two arrays in the Coursera NLP course provided by Stanford University. This algorithm was adopted when merging the same words in the two lists.
Imagine we have two arrays of [1, 2, 3, 4, 5, 6] and [2, 4, 6, 8, 10]. We look to find out the same elements in the two arrays which are [2, 4, 6]. Since there is a ‘Search 1D array‘ function in LabVIEW that can tell if an element is in the array. The implementation of this function is hidden and thus I’m not sure how it was done. Presumebally it iterates through the array and quits either if it finds the equavalent element or reaches the end of the array. So the iteration can take up to N times where N is the length of the array. When we want to compare two arrays with the lengths N and M respectively, the iteration could take up to N*M times.

I prepared two arrays with the lengths of 100k and 90k and used LabVIEW ‘Search 1D Array’ function to find out the same elements. See the code below:
test0
The code iteratively checks if the element of 90k array can be found in the 100k array, and remove the element in the 100k array if found. The running time for the above code is about 7.3 seconds on my desktop. Because the arrays size is large, it could take up to 100,000 * 90,000 = 9,000,000 iterations to calculate this.

An alternative way of doing this is explained in the course. This algorithm moves both arrays simultaneously and thus the running time is much shorter. An illustration screen capture is shown below:
algorithm
The two arrays compare the first elements from the beginning, and both move forwards if the two elements are equivalent. If the values do not match, move the array with the smaller value and carry on comparing with the next value. This calculation takes up to N + M (the sum of the two lengths) iterations. When the array are large, it saves a lot of time.
Following is the seudo code of the ‘merge’ algorithm.
Capture
Here is the LabVIEW implementation.
Find duplicates
And the test VI:
test2
This code takes 0.03 second to compute, which is more than 200 times faster!:D Although we put the ‘Sort 1D array‘ function before hand, it still beats the first algorithm. This code also works well with text arrays (you need to change the input data type of course). Try it out yourself.:)

Tags : ,

小斌

距离上一篇中文博客过去四五年了吧,期间发生了很多值得记录的事情,包括博士毕业,结婚,博士后,从学校到公司,从诺丁汉到伦敦等等。其中对我影响最大的,是我的发小,我最好的朋友,斌,在11年9月去世了。

我曾经想过出席他的追悼会的场景,然后知道这种白发人送黑发人的情况在我们那里是没有追悼会的,甚至没有进墓地。为避免斌母亲的伤心,家里也没有遗像。于是当我赶回去的时候,却找不到可以哭的物件。

斌在11年初被查出得了M5B型白血病。我侄女小时候得过白血病,邻居刘叔也得过,后来都医好了,所以我第一反应是还有得治。但听说他们是M2和M3型,属于相对容易治好的,而M5B听上去就很吓人,查一下之后发现确实很难医治。加上他那时身体和精神状态都不好,没到一年时间居然就走了。消息来得非常突然,正是我答辩之前,我以为答辩之后可以回国看他,没想到错过了与他的最后一面。

我和斌在幼儿园就是同学,但当时印象并不深,是后来看相片才记得。上了小学之后因为我妈和斌的妈妈是商场的同事,我们放学后都会去商场的储物间写作业,开始熟悉一些了。当时达和铁蛋是我们共同的好友,星期六晚上会在家属区一起摸黑玩电报机打响和三个字。小学三年级开始参加各种活动,和斌一起报了美术班,当时发现这个同学居然是左撇子,有时还会被老师纠正。在学画的日子里,有时放学了我们会跑到一处三角造型的屋子外,往墙上跑比谁脚放的高。斌胆子小,每次都是我赢,感觉斌很羡慕的样子。像那时的很多小孩一样,斌学了画画,好像也学了钢琴,但是坚持的都不算久,尝试培养些艺术细胞但还是要让位时间给家庭作业。

那时为了要长高,很多男生开始学打篮球,我和斌也不例外,一起的还有达和铁蛋。那时铁蛋最高,斌第二,我和达都是小个子,于是4个人开始了明确的位置划分。铁蛋的篮球知识开始的最早,我也有样学样地开始背一些NBA的队名来。斌的左手天赋这时发挥了出来,总会让防守的人很难受。我们开始跟一些五六年级的大孩子打球,斌和铁蛋因为个子高一些,通常会在我和达之前被选走。

小学的几年我和斌并不是十分亲密,一直没有在一个班级,一般是有达和铁蛋的场合我俩才会见。一直到六年级,因为班主任离职我们班级被打散重分,我被分到六年一班——斌和达在的班级。我还记得在篮球场上达听说我要去一班说:“太好了!”,斌说:“完了,以后名次又得往后一名。”我充幽默地回答:“没事,你倒着数就不变了。”六年级下学期我就转学了,所以我俩只同班过一个学期——我和铁蛋也是只同班过六年级的下学期。不记得因为什么,我和斌从此就走的近了。可能因为我俩那时上下学有几百米一样的路线,可能因为所谓“成绩好”的同学间会自然亲近,可能是因为我们总在一起打篮球,在转学之前斌和我就是会互相透露喜欢的女生的哥们儿了。之后虽然转学,但是我每天跑通勤,周末了会找斌一起写作业,打球,聊我在那边的状况。斌是个很好面子又很要强的人,成绩一直不错,而我那时成绩更好一些,所以他也爱问我问题。他和另一同学季是我那时仅有的两个平时聊天还会聊到作业上去的朋友。

之后我们便上了不同的初中,斌在的初中是以严厉闻名的,上楼梯时如果跳着上都会被抓到扣分罚钱,整个学校的气氛诡异地紧张,时不时还会有学生老师互殴的情况。对比之下我在的初中就似乎正常多了。于是我们每次碰头都会听他吐槽一下年级组又发生了什么奇葩的新闻,我这边有什么新奇的事,他最近喜欢上了哪个女同学,我最近对谁动心,这道课后题怎么做等等。大多时候斌是倾听者,我是那个侃侃而谈的人,所以他对于我的情况的了解远大于我对他的了解。初中之后斌开始紧张成绩了,他的成绩跟季差不多,不够重点高中的线,但使点儿劲又可以够到的样子。我也听说他喜欢上我小学时的一个同桌,后来那位同桌又和一个小痞子好上了。他也一直听我诉说我初中暗恋的那个女生,听我说有的没的和那女生的故事。有时我的初中同学会来我家玩,和斌一起,斌对他们很熟悉,因为都是我说过的故事。我非常享受能有这么一个树洞可以分享我的内心戏,又不至于被捅篓子。于是周末有时我会住在他家,或者他住在我家。斌的个子开始长起来,到了175,176的样子,随之而来的是满脸的青春痘。斌是我朋友里脸上痘最多的人,这简直一度成为他的标志,也一直困扰着他。作为一个内心敏感又正值青春期的男生,满脸的痘痘简直是杀手一样的存在。斌和他家里开始到处看医生找偏方,想方设法能让脸上光滑一些。

那时我留的是学生头,刘海刚好到眉毛,乖乖地挡在额头上。斌说我头发软,总喜欢边说边从后脑勺鼓捣我头发——这一现在看来很基的举动——然后手被我打掉。我俩见面总会上演类似NBA开场前的庆祝仪式,四手互搏那样的一套拳法,打上一通套路并且每次都乐此不疲。打篮球的还是我们几个,斌这时已经有模有样了,好像是他们班队的,而我初中个子太矮,还是处于被挑剩的角色。斌有个篮球,火车头牌,深色的,特别硬,可能是专门给外场设计的。每次他都会带着那个篮球,伴着咣咣的拍球声出现在球场。球太硬,很容易杵手的那种,但是很耐打。比起铁蛋的印着森林狼而死活不肯拿出来用的橡胶球,这颗球倒是出镜率很高。斌强调说他这颗球虽然很硬,但是确是皮的。达也有一颗球,难得的斯伯丁的,只要有达的球在这个球都是第一选择。所以没多久达的球就磨薄了,有几处鼓了出来。

初中时我喜欢听徐怀钰的歌,因为一次和同学唱歌的时候听到了觉得很好听,那时喜欢的女生也在场,于是移情地也喜欢上了徐怀钰。那时网络还不流行,我是年级里少有的家里有电脑有能上网的人,于是通过雅虎找到了许多关于徐怀钰的个人网站(那时很多网站还是个人维护),并和斌一起分享这份乐趣。我说我喜欢听她的《你还记得吗》和《我不要》,斌也觉得好听。斌和铁蛋那时因为电脑的原因总跑到我家里,软磨硬泡地非要玩几局大富翁或是上几个娱乐网站看一看穿三点式的女星们。

后来我俩又上了不同的高中。我在一高,所谓的重点中学,在一个魔鬼班主任的班里。斌上了三高,就在我们高中隔壁,每天跑通勤。周末时我们还是会碰头,他跟我说他喜欢班上一个很漂亮的女同学,我跟他说我目前好像没什么想法。寒暑假时间虽然短,但那是我们可以好好聊的日子。暑假时我们会一起到家属院门口的一家冰激凌店,看穿吊带的年轻女服务员帮我们盛上两斤冰激凌,一直吃到浑身发冷。有时约上达和铁蛋去临街的一家“荷兰铁板烧”——不知道这家桌子满是油的铁板烧店为什么取这个名字。斌总会提醒说放几个鸡翅在烤盘下边,味道特别好。铁蛋和达那时喜欢摇滚,俩人有时会交流一些我和斌听不懂的话,他俩的成绩也一直不理想。斌在高中属于少有的没有掉队的学生,和季一样,骨子里有股要强的劲儿。有时斌会跟我感慨,在的中学不一样,以后的路也许就不同了。去北京参加一次夏令营后,我有时会说起北京如何如何好,以后多么希望考到北京,他便会无奈地说自己的成绩恐怕进不了北京了。我当然希望能和他一起去北京,于是总给他打鸡血说好好学习争取一起进京。

他给我看过他高中喜欢的女生的照片,确实很漂亮,我也希望他能追到这个女生。那时男生心中大多认为如果我的成绩够好,女生应该会喜欢我了,于是这也成了他学习的动力之一。而斌脸上的包并没有见消,还在搽着各种不知道哪搞来的药,每次我妈见了就会说你不要搽哪些乱七八糟的东西了。我后来脸上也起了癣,花花的,于是有时我会讨问他应该搽点什么。癣下去之后又长了两个大包——不是很密,但是很大。我俩谁也没法笑话谁了,都在偷偷试着各种偏方。斌有一次跟我说《天黑黑》好听,还唱给我听,我听了并不觉得,后来听了遍原唱也没觉得好听。我跟他说我觉得《机车女孩》好听,唱给他听,他听了说有意思然后也开始学。

我又开始跟他讲我高中班的故事,有多么多么变态的班主任,和很多古怪而牛逼的同学。他似乎羡慕有牛逼的同学做朋友,对这些故事听的特别认真。

高考结束,我去了北京,他去了大连——考的不错,去了一所不错的大连的学校。他和季继中考同分之后,高考也只差一分,真是有缘分。季去了阜新,铁蛋和达去了沈阳,我们哥儿几个分开了。高考结束后,斌很感性地写了封电子邮件发到我邮箱,内容大概是说咱们即将属于不同的世界,我很想融入你在的世界但是无奈现实不允许,以后也许要渐行渐远了各自珍重之类的。我回复说不要装逼假期一起去吃冰激凌。后来我俩见面时谁也没有提这档子事儿。

每次放寒暑假我俩都会在对方家里住上一两晚,这成了保留节目。我们还在继续打着球,继续谈论女生,继续YY毕业以后工作的场景。我进了大学开始天天打球,个子不高,但也终于不是初中时的那种嘎嘣豆了,逐渐进入了“乐透区”的行列。再回去碰面打球时,铁蛋和达好像都不怎么打篮球了,玩起了乐队,铁蛋留起了到屁股的长头发,好像突然长了20斤,有点认不出来的样子。斌有时还会打打篮球,但据说他们校园在海边,海风太大,不适合户外篮球了。但是他终于换了颗篮球,深色的火车头报销了,换了斯伯丁的。这个球跻身为我们的第一选择。一次我和斌单挑篮球,他从远处运球朝我跑过来,我便站定位置做出造犯规的姿势。斌躲开我的同时摔倒了,爬起来跟我说,你真的不躲啊?我说你撞到我就是你进攻犯规了啊。斌说:“谁犯规倒是无所谓,给你撞着怎么整。”没想到这句话居然对我影响非常大,之后跟同学打球的时候有了磕碰我都不是第一时间声明谁犯规了,而是看看他是否受伤。不止是篮球,乃至于在生活工作中我也时常想起这句话,并做了无厘头般的延伸——如果我辛勤工作是为了让家人更开心快乐,那么如果因为工作让家人不开心了我就宁可不要去做了。用现在的话来说,就是不忘初心吧。

他说他和那个高中时喜欢的女生还会有书信来往,但是那女生已经有了男朋友,他俩没可能了。然后我跟他说我想追大学班里的一个女生,感觉她对我也有点儿意思,谁知过几天她又不理我了之类的。斌学的是计算机和土木的双学位,本科要5年,他在想毕业后是继续读研还是找工作。我们——斌,铁蛋,达和我——碰头时还是去那家“荷兰铁板烧”,点上一份鸡翅放在烤盘底下。除了斌,我们仨都能喝点儿,斌酒精过敏,有一次喝了一口酒脸红的跟什么似的。斌脸上的包没有再继续长了,因为终于长满了。偶尔有消下去的取而代之的就是一个坑。到了大三大四我脸上的包下去了,虽然坑坑洼洼一些,但是跟斌比起来算是光滑多了。有时我们回家了会去泡澡,在东北这项娱乐现在还在流行。斌觉得每次蒸桑拿之后脸上的包似乎都能好一些,但是在我看来不过是油光少了点儿。

到大四的时候我跟斌说我可能会出国,想去美国,虽然我绩点不高去美国也申不了好学校,但是想圆儿时的出国梦。这个任性的想法是因为有家里的支持,那时家里条件还不错,爸妈觉得有能力供我出国读个研究生。斌说他觉得大城市压力太大,在父母身边挺好的,以后大概会回油田找份工作。

后来我申请了英国的一所学校,因为大学和这个学校有合作项目,申起来方便,而我又是个完全不懂规划自己的人。斌开始他第五年的课程。季本科毕业,参加招工考试回到油田。那时回到油田已经不是容易的事,油田效益不好,职工的子女已经得不到任何招聘的优惠政策。达通过市场应聘回到油田,铁蛋则开始了短期的北漂,跟他的舅舅跑起了外景摄像。之后去山东读了个双学位然后回油田找了工作。

出国一年,我结束了研究生课程,阴差阳错地继续在本校读博。斌毕业后和季一样,通过招工考试进入油田——就在离我家不到两公里的地方上班。复活节放假回家,我和斌在家属区的篮球馆里又来了次1对1。打累了坐在地上,他问我在国外的生活和今后的打算。我说我可能要读博了,之后的几年没什么其它打算。回到英国后不久就听说他没去单位报到而改考陕西一所高校的研究生了,他和我说起来为什么改变了主意:“和你打完那次球之后我坐在馆子里望着天花板想,我以后是不是一辈子都要在这个馆里打球了?”大概觉得这不是他想要的生活,于是放弃了回油田工作的机会,自己跑到西安了。

之后我送走一起在英国读研究生的朋友们,自己又留在学校读书。回国的日子比较固定,每年一次1个月的假期,回去后会在北京逗留一个多星期,会一会高中,大学和研究生的同学,然后回辽宁待剩下的两个多星期,看看亲戚朋友,找发小们聚一聚。跟斌联系的不算多。那时还没有微信,只能在QQ上遇到时才聊一阵,彼此的生活轨迹逐渐不同,共同的话题不多了,我很难把英国的生活绘声绘色地讲给他,何况那时生活本来也简单无聊。

我在开始读博时认识了我现在的妻子楠,这也是另一与斌联系渐少的主要原因吧。生活重心逐渐转入二人世界,只是回国的时候会跟斌说我找了个女朋友,人很好,我很喜欢。更多的八卦倒是跟我的高中哥们儿振和两个研究生哥们儿分享了,因为共同的好友多一些。回国时还是肯定会聚一下,但不会去斌家住,因为女朋友也很快被带回来见了家长,之后不久我们就订婚了。

带着楠第一次见发小们已经是订婚一年后的时间了,因为订婚时第二天便匆匆地去了妻子老家,并没有和很多朋友相认。第一次聚时斌有点反常,全不是平时的以问代说的样子,很努力地表现出平时不多见地健谈来,时不时抖出我的糗事让大家笑一笑。比较之下倒显得我好像不那么能说了。我想是因为这是第一次我们这群人里进来个女生吧,他还不是很放松的样子。事后我跟楠说斌平时不是这样的,他总的来说还是个很内向的人。

斌硕士的最后一年他的父亲做了心脏手术,母亲出了车祸,虽然没有生命危险但脑部造成损伤也做了手术。斌硕士毕业后为了照顾父母还是回到了油田,回到他3年前离开的那个单位。他每次跟我说起老妈的车祸时会说:“这咋整呢,没办法,谁叫咱们摊上了呢。”

也许是夜深了,或者人就是对最近的记忆反倒淡了,说起之后几年的回忆我倒想不起来那么多。好像下一个镜头就是2010年年底我跟他说我明年毕业,之后和楠结婚,你来做我的伴郎,之后回到英国。然后第二年1月份的时候,就从母亲嘴里听说斌被查出白血病,而且是很不乐观的M5B型。出国五六年,有几位亲人离开了我,但是我因为打小就跟父母生活在他乡,与亲戚们走动的并不多,听到这些消息时只是难过。听到斌的白血病的那一刻却像霹雳一样,根本不敢相信。又在潜意识里认为他不会有事的,虽然会非常痛苦,但不会有生命危险的。

鼓足了勇气给他打了第一个电话过去,脑子里一片空白不知道该说什么。想让他振作,相信自己会战胜病魔,却说的我自己都没有底气。他说:“你说这事儿怎么让我摊上了呢?”我哭着说不出话来,又怕他听到我的啜泣声。我说没事,现在医疗技术可牛逼了,你就是遭点儿罪,但肯定能医好的。把我的苹果商店账户给他,说你在床上没事儿时可以用我的账户下点儿游戏什么的。斌的爸妈为了他的手术自然四处奔波,对本来就不富裕的家庭来说更是雪上加霜。我妈组织了她们原来商场共事过的同事给斌捐款,我的小学同学也在校内网上号召了捐款。我让那时在北京工作的未婚妻去天津看望正在住院的斌。未婚妻虽然之前只和斌见过一次,但这次见到也难过的不行,跟我说他面容非常憔悴,瘦了几十斤了。我没见过他生病时的样子,没法想象印象中那个一米八的男生瘦到110斤会是什么样。

斌在生病之前谈了对象,在知道自己生病之后就不接那个女生的电话了。女生很心急,前几个星期想方设法联系他,后来心冷了也没有再联系他,两人也没再见面了。

我开始在网上找医院,问朋友谁认识牛逼的医生。但了解的越多越觉得希望渺茫。还会时不时的打电话,老妈说你打电话过去他也许更伤心,我说我也不怕触这个霉头,想让他知道他一直被惦记着。但每次打电话依然战战兢兢,首先过不去自己心里的坎儿,怕自己绝望的情绪传染给他。我并不信偏方,也不怎么信老中医,但跟他说你放心吧,这个西医治不了但是还有中医,那个中医很牛的。中间听老妈说,病情一直没有得到控制,时不时发烧,便血,状态尚维持不下来,更不要提做脊髓手术了。

但还是没想到,非常快地,斌就走了。知道这个消息是从铁蛋的校内状态上。我看到后打电话给铁蛋,说你他妈的瞎说什么,谁没了?铁蛋怔怔地跟我说,哥,你不知道吗?斌走了,昨晚走了,说完扯着粗嗓子哭了。我傻掉了,我觉得这一幕永远不会发生,我觉得在我的人生剧场里,我是男主的话斌就是男二号,男二号永远不可能挂掉的。我捂在被子里嚎啕哭起来。然后我给达打电话,跟他说斌的消息。达已经喝的大醉,跟我说他也知道了,达说他觉得小斌并没走,只是在那儿等着我们哥儿几个,我们几个还是会聚在一起的。达说他现在觉得什么都不重要了,跟生命比起来那都是狗屁。他结结巴巴地说着,酒劲参杂着哭劲。把一句话说完以后我俩都听不到对方说什么,都哭的没法说话了。

斌的妈妈非常低调地处理了儿子的后事,之后用斌的账号登录了校内网,发了一篇帖子告诉大家斌已经离世,谢谢大家的关心和帮助。我不知道斌的爸妈怎么面对以后的生活,我爸说这是永远过不去的坎儿。

我在11年底毕业,和楠领证,又经过两年终于完成婚礼。每次回国时我便去看斌的妈妈,但从来不提斌的事儿,只说我自己的状况,只问他们老两口的身体。然后刚出门就会哭很久,在屋里的斌的妈妈也以泪洗面。我和楠举行婚礼那天,老妈不敢让斌的妈妈看到,怕她伤心,编了个谎让斌的妈妈出门了。我在婚礼的前一天,把我的好哥们儿们找在一起,边喝酒边跟他们说,我今天他妈的特别高兴,我最好的哥们儿都来了,我最大的遗憾就是,我最最好的哥们儿来不了了。上次回国,斌的父母在搬家,我去到新房子,跟斌的妈妈聊了一会儿。出门时看到地上放着斌的篮球,那颗很好用的斯伯丁。我再一次泪崩,赶紧下楼了。

自从斌走了以后,差不多每个月我都会梦到他,到现在已经4年多了,还是不曾落下。每次梦到时都知道他要没了,告诉他一定要小心,然后便拥抱在一起一直到哭醒。每每看到兄弟情深之类的电影,也会忍不住哭出来。

斌的妈妈说当初非常后悔没同意让斌出去闯一闯,也许他心情再好一些就不会得这个病了。我万万没想到斌会走的这么突然,不然博士论文完全可以搁置一下。达说他当初跟斌不该说那些你会好起来的鬼话,因为他自己都不信,不如当初索性问他还有什么想干的事情。世间没有后悔药,而且就算重新发生了也未必就能改变斌的状况。我自我宽慰地想,我们没有上帝视角,没法保证能做出正确选择,只能尽人事听天命。在斌走之前,我碰到事便会自我安慰,事情本可能更坏呢。现在我的自我安慰变成,好歹我还活着。

————————————————————————-

一直想写一篇文章纪念斌,纪念我们回不去的过去。通篇杂乱无章,全是我斑驳的记忆,趁这几天刚做完手术闲赋在家,码下这几千字,全是为了自己留个念想。以后我有了孩子,如果他没有耐心听我说我和我的铁哥们儿的故事,也许他还会翻到这篇文章,耐着性子读下来。

一路走好,小斌。

Hidden Markov Model in LabVIEW

Consider this scenario: a guy (let’s call him John) has three dices, Dice 1, 2 and 3. The shapes of the dices are different. Dice 1 has number [1, 2, 3, 4, 5, 6] on it, Dice 2 has number [1, 2, 3, 4] and Dice 3 has [1, 2, 3, 4, 5, 6, 7, 8], as seen in the following figure.

image6

http://www.niubua.com/?p=1733

John throws one dice each time and the probability he picks the next dice is based on his previous selection. For example, he is more LIKELY to pickup Dice 1 if he just picked Dice 2 last time, and he UNLIKELY to pick Dice 1 if he just picked Dice 3 last time. We do not know which dice he selected but we can see the number shown on the dice. Now, after the observation of a sequence of throwing dices, what do you think the next number would be?

This may sound a very difficult question but actually in linguistics the researchers are dealing with this kind of problem all the time. It’s like you can HEAR the sound of each word every time and based on the HIDDEN connection rule of the words (i.e. syntax and meaning) we want to predict what the next word could be. Mathematical models were built to represent this type of question. In this example, the states are determined by its previous state(s) and we call it Markov Model, or Markov Chain. A simple case is the state is determined by its previous one state — a Markov chain of order 1. Also, which dice (state) was selected is not know and instead, the consequence of the state (number) can be observed. It is called Hidden Markov Model.

There are three problems in HMM that need be addressed. They are 1) Evaluation: Given the probability of the state transmission and the probability of the shown observations of each hidden state (I.e. for a given HMM), calculate the probability of an observed sequence.  2) Decoding: Given the HMM and the observed sequence, what is the most likely hidden states happened behind this. 3) Learning: Given the observed sequence, estimate the HMM. As we can see from this, the third problem is the most difficult one.

Hidden Markov Model (HMM) is a powerful tool for analyzing the time series signal. There is a good tutorial explaining the concept and the implementation of HMM. There are codes implementing HMM in different languages such as C, C++, C#, Python, MATLAB and Java etc. Unfortunately I failed to find one implemented in LabVIEW. This may be a reinvention of the wheel, but instead of calling the DLLs in LabVIEW, I built one purely in LabVIEW with no additional add-ons needed.

Multiple references were used to implement this LabVIEW HMM toolkit. [1], [2], [3], [4]. The test demo of forward algorithm, backward algorithm and Viterbi Algorithm in the code referenced [2].

The following demo analyzed the hidden states of a chapter of texts. You can find the detailed description in [1]. The following figure is the observed sequence of the HMM model. There are about 50,000 characters (including space) in this text. All punctuations were removed and only the space and letters were kept as the hidden states. Thus there are 27 states, State 0 to 26, of which State 0 = Space, State 1 = a/A, State 2 = b/B and so on.

Sample

With no prior knowledge of this text, or even English, we initialize a HHM model that has two hidden states. The probability of propagating from one state to another is unknown yet. The 26 letters are the observed phenomenons of the hidden states. The probability of each letter in State 1 is plotted in dots, and the probability of each letter is plotted in line in the 2nd state.

Init b

Running the forward-backward algorithm in HMM we obtained two states: Letters A, E, I, O, U more likely to appear in State 1 while the rest letters more likely to appear in State 2. So with no specified rules or prior knowledge we managed to divide the letters into vowels and consonants.  🙂

Final b

[1] https://www.cs.sjsu.edu/~stamp/RUA/HMM.pdf
[2] http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html
[3] http://www.52nlp.cn/hmm-learn-best-practices-one-introduction (Chinese)
[4] http://www.kanungo.com/software/software.html#umdhmm

 

 

 

 

Tags : , , ,

Get the old Pocket button back for Firefox

Firefox has integrated the Pocket button into the browser since version 38.0.5. You can take out the Pocket button by navigating to the customize button of Firefox.

But I just don’t like the new design. I cannot tell if a webpage was Pocked already or not when I browsed it the second time. And I had to open up a web page to view my Pocked list. So I decided to take the old Pocket button back (sorry, Mozilla). If you feel the same way, you can download the old Pocket add-on file for Firefox from here. Please leave a comment if you have difficult downloading this file and please identify your region.

After you download this file, you shall be able to install it by simply double clicking. If not, go to the Add-ons page in Firefox, click the gear (‘tools for all add-ons‘) icon on the top-right, select ‘Install Add-on From File…‘ and select the downloaded .xpi file.

Enjoy your retro Pocket button 🙂

 

Tags :

Sitemap

Pages

Posts by category

THE personal blog site

Hi all, sorry that I haven’t been updating the posts for a long while (again!) and I just moved my blog from foolooo.wordpress.com (again!) to here. Now finally I have a blog site hosted on my own computer — well, not really my computer, I just rent this server. And what is cooler is I have my own domain name now 🙂 So people from both China (GFW issue) and all other countries around the world can visit this website with no problem.

Another reason I moved my blog is I kinda look for some place to merge both the techy blogs (previous Let’s LabVIEW) and the personal blogs (previous FoOl’s BlOg) so that it’s easier to maintain in the future. I also try to learn/write more things in Machine Learning, Computer Vision and Natural Language Processing which do not have to be in LabVIEW.

This website is just built and still under construction. More widgets need to added in and a better name may come up soon. Hope to keep in touch. Thanks all.

Cheers,
Bo

Two tiny functional VIs

For the last a few months I am still learning Machine Learning with LabVIEW (which might not be the best language for ML) and doing more signal processing jobs. I tried to follow some MOOC courses on R and Python to master better tools for ML. Really got some to-do projects in my mind and want to implement them soon.

Since I am dealing with a lot of file loading recently, this vi was built to scan a folder to find the file starts with the specific string. This is nothing complicated and I am sure there is a simpler solution. But here is an example of the implementation:

Find file starts with the name

It iterates the names of the files and quits if finds the name starts with the “Start with” string.

Another function is “Random selection from elements“. It allows the user to randomly select from their own dataset, which could be a number of integers, strings or any other data types. Again this is very simple but I found it quite useful in many “simulation” applications.

random element

The input array can be replaced by any other types of arrays. It is worth mentioning there is a “Riffle.vi” in LabVIEW that can randomly disorganize the input elements (so the output is a disorganized array). The randomness can be repeated by setting the seed to the same number.

 

 

Genetic Algorithm in LabVIEW to solve the shortest path routine problem

I came across Genetic Algorithm (GA) the other day when I was doing the project. It is typically adopted to solve the shortest path routine problem or design and optimize the structure of proteins. It is a very smart algorithm inspired by the biological system.

I will try to describe the idea behind the concept briefly: In some problems there are many possible solutions, and we look for the best one. To find this very best solution it is like creating the chromosome of the genes in the most optimized order. To find out the best (-ish) combination, one way is comparing ALL possible combinations, which is impractical in some cases.  So instead of listing all solutions and comparing them, a sub-group of solutions (population) are created, and then we pick two out of them as the parents. The better the solution was, the higher chance it can be selected. Then the two chromosomes crossover (exchange genes) to “breed” new populations. There is a chance of mutation for the new population as well. The new population are usually more “advanced” than their parent population (not necessarily better than their parents). Then new parents are picked out again to breed new populations and so on.

Typically the genes to order in the chromosome are binary, but we can also do that for integer numbers and other values. Please find this tutorial for more encoding methods.

To demonstrate the implementation of GA in LabVIEW I downloaded the coordinates of 31 cities of China and tried to find out the shortest path routine of them. So here is the .gif demo (the labels for X and Y axises should be “Latitude” and “Longitude”). Please note that this may not be the BEST solution. But in term of the number iterations we ran it, it is good enough.

 

Shortest path routine for 31 cities in China
Shortest path routine for 31 cities in China

You can download this code here:Genetic Algorithm. Please rename it to .zip file and unzip it.

Let me know your score 😉

 

 

Tags : , ,

A quick update for the Flappy Bird project

It seems last post was found by @labview and brought much visiting here. So this project is still undergoing and I was kind of busy this month. But I will try finish this ASAP 🙂

Here are some updates since last post.

An Arduino controlled stylus now can be controlled by clicking the mouse.

Image

There is a tip that the stylus needs to be earthed (via the red wire) to take affect.

And the Flappy Bird game is (poorly) simulated on LabVIEW. So I simulated FB (not facebook!) on LabVIEW to test the Q-learning algorithm in a purely software environment. Now it can pass 5 gaps 🙂 The algorithm needs to be altered a bit and then I will integrate the whole things.

Image

Tags : , ,

Implement Q-Learning algorithm in LabVIEW

So this is the story: Flappy Bird was so popular that my friend suggested that we should develop a LabVIEW kit with a motor to play it. Two days later, we found Sarvagya Vaish managed to score 1000 by applying Q-learning algorithm. A couple of days later, a studio used arduino to play the game. Hmm…I will finish my work anyway.

That’s where I learned about the Q-learning, one of the reinforcement learning algorithm. Here is a brief tutorial helped me to have a better understanding of it. So if a goal is achieved by multiple steps, this algorithm grades each step by assigning a reward to it. Each step, or action, is not graded right away, but one step later. In this way the “right” action can be determined by the reward it received.

The equation can be described as
Q'(s, a) = (1 – alpha)*Q(s, a) + alpha*(R(s, a) + Gamma * Max[Q(s’, all a’)])

Where Q (accumulative experience) is a table of s (state) and a (action), s’ is the next state and a’ is the next action. alpha is the step size and Gamma is the discount reward. I tried to google a Q-learning example in LabVIEW but failed. So I created this vi myself and hope it can be useful to someone.

Image

This is a single loop vi and the shift register stores the value for Q. The reset button is to initialize Q’s value and can be replaced by “first call?” node. The user shall build their own “Reward” vi according to their applications. In this vi the next action is determined by the Q value that rewards the most but it can also be a random action (or other methods).

Please find the tutorial links 1 2 for more information about Q-learning algorithm.

Tags : , , ,