LZW

Note: It has been pointed out that there is a problem that occurs when encoding strings of consecutive characaters e.g. 1111111111 - I will fix this when I get a chance

Try out LZW data compression using my PHP implementation below - try encoding the article taken at random from Wikepdia or input your own text for encoding.

LZW doesn't work well with short strings. Try encoding 'hello'!

Random Article From Wikipedia: Timothy Warren Anglin (August 31, 1822 . May 4, 1896) was a Canadian politician and Speaker of the Canadian House of Commons.

Born in Clonakilty, County Cork, Ireland, Anglin emigrated at the age of 26 as part of the exodus caused by the Irish Potato Famine. Following a sectarian riot in New Brunswick between members of the Orange Order and Catholics, Anglin appealed for moderation and unity. This led him to take up the editorship of a new newspaper, the Freeman, which made him an influential voice in the colony. He was elected to the Legislative Assembly of New Brunswick in 1861, and became an opponent of Canadian Confederation and of the government of Samuel Leonard Tilley which he helped defeat in 1865. Tilley returned to power the next year, however, with the defeat of the Anti-Confederation Party in the election. Anglin lost his own seat.

New Brunswick entered Confederation as a province in 1867 and Anglin won a seat in the new Canadian House of Commons as a Liberal Member of Parliament (MP) for the riding of Gloucester in the country's first general election.

When the Liberals came to power in the 1874 election, the new Prime Minister of Canada, Alexander Mackenzie, nominated Anglin as Speaker of the Canadian House of Commons.

Anglin's term as Speaker was controversial. The Speaker is expected to act in a non-partisan manner and be above politics, but Anglin used his rulings as Speaker as opportunities to enter into partisan debate. Even more troubling to the opposition was the fact that he retained his position as editor of a partisan newspaper during his term as Speaker, and used his position to write editorials berating the Opposition. Especially controversial was the fact that his newspaper was given government printing contracts. Anglin was accused of violating the Independence of Parliament Act for accepting government printing contracts, and was censured by the House of Commons Committee on Privilege in 1887. Anglin was forced to resign as Speaker and as an MP, but was re-elected to the House of Commons in the by-election that was held to fill his seat. He was successfully renominated by Mackenzie to the position of Speaker.

Anglin's period as Speaker ended with the 1878 election that defeated the Liberal government. He remained in the House of Commons until he lost his seat in the 1882 election. Following his defeat, Anglin moved to Toronto and became editor of the Toronto Tribune. In the 1887 election, he was defeated in his bid to win a seat from the Ontario riding of Simcoe North.

Three of Anglin's nine children were notably successful; Francis Alexander Anglin was Chief Justice of the Supreme Court of Canada from 1924 to 1933, Arthur Whyte Anglin was a successful private practise lawyer, and Mary Margaret Anglin became the first internationally-renowned Canadian stage actress.

The encoded output will hopefully be shorter than the input!

The first 16 bits of the output are used to store the number of bits used to encode each codeword.

Fixed version note

You will notice on this old version that if you encode and decode the text it will not be the same. After a while of debugging I finally noticed (the algorithm looked perfect!) that the problem was caused by the php function in_array that I used to determine if word+x is in the dictionary (see LZW algorithm).

The following code demonstrates the problem:



$myarray = array(" 1", "a");
echo in_array("1", $myarray); //echo in_array("1", $myarray, true); will work correctly

The output is 1 (true) - it seems that in_array trims the string " 1", so that it equates to "1". The fix was simple - use the strict paramater of in_array and it will also check the types. :-)

View Page Source

It's not what you know, it's whoyouknow.co.uk