Tag Archives: Computer science

Computer Algorithms: Data Compression with Diagram Encoding and Pattern Substitution

algorithms, PHP, , , , , , , , , , , , , ,

Overview

Two variants of run-length encoding are the diagram encoding and the pattern substitution algorithms. The diagram encoding is actually a very simple algorithm. Unlike run-length encoding, where the input stream must consists of many repeating elements, as “aaaaaaaa” for instance, which are very rare in a natural language, there are many so called “diagrams” in almost any natural language. In plain English there are some diagrams as “the”, “and”, “ing” (in the word “waiting” for example), “ a”, “ t”, “ e” and many doubled letters. Actually we can extend those diagrams by adding surrounding spaces. Thus we can encode not only “the”, but “ the “, which are 5 characters (2 spaces and 3 letters) with something shorter. In the other hand, as I said, in plain English there are two many doubled letters, which unfortunately aren’t something special for run-length encoding and the compression ratio will be small. Even worse the encoded text may happen to be longer than the input message. Let’s see some examples.

Let’s say we’ve to encode the message “successfully accomplished”, which consists of four doubled letters. However to compress it with run-length encoding we’ll need at least 8 characters, which doesn’t help us a lot.

// 8 chars replaced by 8 chars!?
input: 	"successfully accomplished"
output:	"su2ce2sfu2ly a2complished"

The problem is that if the input text contains numbers, “2” in particular, we’ve to chose an escape symbol (“@” for example), which we’ll use to mark where the encoded run begins. Thus if the input message is “2 successfully accomplished tasks”, it will be encoded as “2 su@2ce@2sfu@2ly a@2complished tasks”. Now the output message is longer!!! than the input string.

// the compressed message is longer!!!
input:	"2 successfully accomplished"
output:	"2 su@2ce@2sfu@2ly a@2complished tasks"

Again if the input stream contains the escape symbol, we have to find another one, and the problem is that it is often too difficult to find short escape symbol that doesn’t appear in the input text, without a full scan of the text. Continue reading Computer Algorithms: Data Compression with Diagram Encoding and Pattern Substitution →

Computer Algorithms: Sequential Search

algorithms, javascript, PHP, , , , , , , , , , , , , , , , ,

Overview

This is the easiest to implement and the most frequently used search algorithm in practice. Unfortunately the sequential search is also the most ineffective searching algorithm. However, it is so commonly used that it is appropriate to consider several ways to optimize it. In general the sequential search, also called linear search, is the method of consecutively check every value in a list until we find the desired one.

Basic Implementation

The most natural approach is to loop through the list until we find the desired value. Here’s an implementation on PHP using FOR loop, something that can be easily written into any other computer language.

This is really the most ineffective implementation. There are two big mistakes in this code. First of all we calculate the length of the list on every iteration of the array, and secondly after we find the desired element, we don’t break the loop, but continue to loop through the array.

Forward Linear Search

Yes, if the element is repeated without the “break” we can find its last occurrence, but if not the loop will iterate over the end of the array with no practical value.

Optimization of the forward sequential search

… and javascript:

Optimized forward linear search

Even with this little optimization the algorithm remains ineffective. As we can see, on every iteration we have two conditional expressions. First we check whether we’ve reached the end of the list, and then we check whether the current element equals to the searched element. So the question is can we reduce the number of the conditional expressions?

Searching in reverse order

Yes, we can reduce the number of comparison instructions from the forward approach of the linear search algorithm by using reverse order searching. Although it seems to be pretty much the same by reversing the order of the search we can discard one of the conditional expressions.

Note that we need to adjust index because of $index—expression.

Indeed here we have only one conditional expression, but the problem is that this implementation is correct ONLY when the element exists in the list, which is not always true. If the element doesn’t appears into the list, then this code can lead to an infinite loop. OK, but how can we stop the loop even when the list doesn’t contain the desired value? The answer is, by adding the searched value to the list.

Sentinel

The above problem can be solved by inserting the desired item as a sentinel value. Thus we’re sure that the list contains the value, so the loop will stop for sure even if at the beginning the value didn’t appear to be part of the list.

Using setinel in sequential search

This approach can be used to overcome the problem of the reverse linear search approach from the previous section.

Complexity

As I said at the beginning of this post this is one of the most ineffective searching algorithms. Of course the best case is when the searched value is at the very beginning of the list. Thus on the first comparison we can find it. On the other hand the worst case is when the element is located at the very end of the list. Assuming that we don’t know where the element is and the possibility to be anywhere in the list is absolutely equal, then the complexity of this algorithm is O(n).

Different cases

We must remember, however, that the algorithm’s complexity can vary depending on whether the element occurs once.

Is it so ineffective?

Sequential search can be very slow compared to binary search on an ordered list. But actually this is not quite true. Sequential search can be faster than binary search for small arrays, but it is assumed that for n < 8 the sequential search is faster.

Application

The linear search is really very simple to implement and most web developers go to the forward implementation, which is the most ineffective one. On the other hand this algorithm is quite useful when we search in an unordered list. Yes, searching in an ordered list is something that can dramatically change the search algorithm. Actually searching and sorting algorithms are often used together.

A typical case is pulling something from a database, usually in form of a list and then search for some value in it. Unfortunately in most of the cases the database orders the returned result set and yet most of the developers perform a consecutive search over the list. Yet again when the list is ordered it is better to use binary search instead of sequential search.
Let’s say we have a CSV file containing the usernames and the names of our users.

Username,Name
jamesbond007,James Bond
jsmith,John Smith
...

Now we fetch these values into an array.

// work case
$arr = array(
    array('name' =&gt; 'James Bond', 'username' =&gt; 'jamesbond007'),
    array('name' =&gt; 'John Smith', 'username' =&gt; 'jsmith')
);

Now using sequential search …

// using a sentinel
$x = 'jsmith';
$arr[] = array('username' =&gt; $x, 'name' =&gt; '');
$index = 0;

while ($arr[$index++]['username'] != $x);

if ($index &lt; count($arr)) {
    echo "Hello, {$arr[$index-1]['name']}";
} else {
    echo "Hi, guest!";
}

Looping Animation with JavaScript and Raphaël

javascript, micro tutorial, , , , , , , , , , , , ,

Raphael is a popular JavaScript library helping you to manage vectors via SVG or VML in your browser. It is extremely helpful and very easy to learn and use. The interesting thing is that in the browser you can do very powerful things with vectors, but they remain very less known. However with such libraries like Raphael the task is really simple.

Animation

As I said animating some vector properties is as simple as:

var paper = Raphael('canvas', 1024, 500);
var c = paper.circle(50, 50, 6).attr({fill : '#f00'});
c.animate({r : 10, fill : '#00f'}, 1000);

Here we change the radius and the background color of the circle for 1000 milliseconds.

The same thing can be done with any property with any other JavaScript library as jQuery. But as in jQuery, Raphael or whatever library the animation is not looping. That’s natural you can just change a property by animating it, but the looping animation suggests at least two animations. So it’s a developers job to implement this. Here’s a simple way to do this.

Two Way Animation

The solution here is using two functions calling each other.

var paper = Raphael('canvas', 1024, 500);
var c = paper.circle(50, 50, 6).attr({fill : '#f00'});
 
function a() {
    c.animate({r : 10, fill : '#00f'}, 1000, b);
}
function b() {
    c.animate({r : 6, fill : '#f00'}, 1000, a);
}
a();

JavaScript Flexibility – Regex match()

javascript, micro tutorial, , , , , ,

Today after two posts [#1, #2] in the past days here’s something that shows again the JavaScript power. This is not a complete example, but it’s good to start.

var str = '/text/1/text/2/';
var a = str.match(/(\d+)/gi);
console.log(a);

in that example you’ll get an array with all the numbers in the string [“1”, “2”] – yet another flexible js snippet!

Flexible JavaScript – Replace in a String

web development, , , , , , , , , , ,

Here’s yet another example of the JavaScript flexibility. You can simply call .replace() on every string and pass a regex as a parameter!

var str = 'my simple string';
str.replace(/ /g, '-'); // now 'str' will contain 'my-simple-string'