Posts

Showing posts from 2014

Unique prefixes

Image
This is a problem about finding the shortest unique prefixes for a list of words.


To illustrate this, bellow is an example with the prefixes highlighted:

playingplayer
To solve this problem, we are going to implement a generic algorithm which will work for any number of words. A very fast way of doing this, is by using multidimensional hashes.

The simplest way to create a multidimensional hash, is to create a reference to the original hash, iterate over the keys you want to add and create a new hash for each key which doesn't exists inside the current hash, and change the hash reference to this new hash.

Let's define a function which takes a reference to a hash and a string. First, it splits the string into characters, then it traverses the hash, adding each character to the corresponding branch:

subadd_entry{my($ref,$word)=@_;foreachmy$char(split(//,$word)){$ref=$ref->{$char}//={};}}
Now, let's define an %hash and call the above function to add an 'word' into it: …

Sidef Programming Language

Image
Sidef is a modern, open-source, object-oriented programming language, fully implemented in Perl.
Book: https://trizen.gitbooks.io/sidef-lang/content/Tutorial: https://github.com/trizen/sidef/wikiRosettaCode: https://rosettacode.org/wiki/Sidef ** ** **** * ********* ********* * * ** * * **** ** ** ** ** ** ** ** ** ** **** *** ********* * * * ** ** ** **** * * ****** ****** * * * * * * * * * **** ** ** ** ** ** ** ** ** ** **** ****** ****** * * ** ** **** * * * ********* *** * * ** * * **** ** ** ** ** ** ** ** ** ** **** ********* ********* * Main features of the language include:variables, constantsmodules, classesmetaprogrammingloops, conditional expressionslazy Boolean operat…

LZ compression

Image
The LZ compression family include a large variety of lossless data compression algorithms, all derived from a very simple algorithm created by Abraham Lempel andJacob Ziv in the late '70s, known as LZ77.



The algorithm is elegant and very dynamic and works excellent on very large input streams, producing the encoded output right away, ready to be decoded at the other end. Many websites are compressed with this algorithm, which reduces their size considerably with almost no cost regarding the decompression time.

In this post, we are going to take a look at a new algorithm, very similar with LZSS, called LZT.

Compression

The compress() function takes two arguments: the input stream, which can have any length, and the output stream which is ready to receive the encoded data chucks.

Input :TOBEORNOTTOBEORTOBEORNOT#
Output:TOBEORNOT[0,6][0,9]#


Steps of the algorithm:

Read 256 bytes from the input stream.Create a new dictionary containing the positions of the longest repeated sub-strings.Writ…

fbrowse-tray

Image
fbrowse-tray: browse the filesystem through a Gtk2 status icon (related to obbrowser).


The filesystem is browsed recursively, but lazily, which means that a directory's content will be read only after hovering the mouse over a submenu entry.
Githubhttps://github.com/trizen/fbrowse-tray
AURhttps://aur.archlinux.org/packages/fbrowse-tray/