Create Vector images using Bit Arrays in Java

Hello Everyone,

Today I will show you how to create a simple image by using code in Java in Applet. I have used Netbeans IDE 7.3 beta 2 and Java 7. You must have a bit knowledge about java and Applets for you to understand this code properly.
We will create a simple smiley and a hut. To create a simple hut or smiley we have to create a pixel array of the image which we will use to create a image. We will make a pixel Array of 16 X 16 bit as shown in the image below..
 

If you use an IDE like Netbeans or eclipse then you can see the image as an IDE traces out similar variable and highlights them and so it will be easier for you to create them.

we create two object of image class in which the image will be stored or created.

Image smiley;
Image house;

Next we instantiate the colors we want to use for displaying the image

protected static final int w = Color.white.getRGB();
protected static final int y = Color.yellow.getRGB();
protected static final int b = Color.black.getRGB();
protected static final int r = Color.red.getRGB();
protected static final int g = Color.green.getRGB();

Here are the pixel arrays for hut and smiley1 = :) and Smiley2 = :P

protected static final int imageData[] = {
        w, w, w, y, y, y, y, y, y, y, y, y, y, w, w, w,
        w, w, y, y, y, y, y, y, y, y, y, y, y, y, w, w,
        w, y, y, y, y, y, y, y, y, y, y, y, y, y, y, w,
        w, y, y, y, b, b, y, y, y, y, b, b, y, y, y, w,
        y, y, y, y, b, b, y, y, y, y, b, b, y, y, y, y,
        y, y, y, y, y, y, y, y, y, y, y, y, y, y, y, y,
        y, y, y, y, y, y, y, y, y, y, y, y, y, y, y, y,
        y, y, y, y, y, y, y, y, y, y, y, y, y, y, y, y,
        y, y, y, y, y, y, y, y, y, y, y, y, y, y, y, y,
        y, y, y, b, y, y, y, y, y, y, y, y, b, y, y, y,
        y, y, y, y, b, y, y, y, y, y, y, b, y, y, y, y,
        y, y, y, y, y, b, b, y, y, b, b, y, y, y, y, y,
        w, y, y, y, y, y, y, b, b, y, y, y, y, y, y, w,
        w, y, y, y, y, y, y, y, y, y, y, y, y, y, y, w,
        w, w, y, y, y, y, y, y, y, y, y, y, y, y, w, w,
        w, w, w, y, y, y, y, y, y, y, y, y, y, w, w, w
    };

protected static final int imageData2[] = {
        w, w, w, b, b, b, b, b, b, b, b, b, b, w, w, w,
        w, w, b, g, g, g, g, g, g, g, g, g, g, b, w, w,
        w, b, g, g, g, g, g, g, g, g, g, g, g, g, b, w,
        b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b,
        b, y, y, y, y, y, y, y, y, y, y, y, y, y, y, b,
        b, y, y, y, y, y, y, y, y, y, y, y, y, y, y, b,
        b, y, y, b, b, y, y, r, r, y, y, b, b, y, y, b,
        b, y, y, b, b, y, y, r, r, y, y, b, b, y, y, b,
        b, y, y, y, y, y, y, r, r, y, y, y, y, y, y, b,
        b, y, y, y, y, y, y, r, r, y, y, y, y, y, y, b,
        b, y, y, y, y, y, y, r, r, y, y, y, y, y, y, b,
        b, b, b, b, b, b,  b, b, b, b, b, b, b,  b, b, b,
        w, w, w, w, w, w, w, w, w, w, w, w, w, w, w, w,
        w, w, w, w, w, w, w, w, w, w, w, w, w, w, w, w,
        w, w, w, w, w, w, w, w, w, w, w, w, w, w, w, w,
        w, w, w, w, w, w, w, w, w, w, w, w, w, w, w, w
};

protected static final int imageData3[] = {
        w, w, w, y, y, y, y, y, y, y, y, y, y, w, w, w,
        w, w, y, y, y, y, y, y, y, y, y, y, y, y, w, w,
        w, y, y, y, y, y, y, y, y, y, y, y, y, y, y, w,
        w, y, y, y, b, b, y, y, y, y, b, b, y, y, y, w,
        y, y, y, y, b, b, y, y, y, y, b, b, y, y, y, y,
        y, y, y, y, y, y, y, y, y, y, y, y, y, y, y, y,
        y, y, y, y, y, y, y, y, y, y, y, y, y, y, y, y,
        y, y, y, y, y, y, y, y, y, y, y, y, y, y, y, y,
        y, y, y, y, y, y, y, y, y, y, y, y, y, y, y, y,
        y, y, y, b, y, y, y, y, y, y, y, y, b, y, y, y,
        y, y, y, y, b, y, y, y, y, y, y, b, r, y, y, y,
        y, y, y, y, y, b, b, y, y, b, b, r, r, y, y, y,
        w, y, y, y, y, y, y, b, b, r, r, r, r, y, y, w,
        w, y, y, y, y, y, y, y, y, r, r, r, r, y, y, w,
        w, w, y, y, y, y, y, y, y, r, r, r, r, y, w, w,
        w, w, w, y, y, y, y, y, y, y, r, r, y, w, w, w
};

Here's the complete code :-

Here is the resulting output image :-

How this will help you ?

This will help you in many ways. Suppose that you are writing some kind of game and with this you can make your own gaming vectors like arrows, pointers, small cars or human figures. Even of you wan then you can colorize these, it depends upon the programmer on how will he/she is able to apply a concept.


Have fun coding.

Thank you,
Sincerely,
Psycho_Coder

Related articles

• Recommended Books to become a Java Hero from Java Zero
• Java Code to read Character File using FileReader.
• Visual Stack Application in Java
• Math Expression Parser in Java
• 5 Most Funny Java Videos on Youtube
• PDF File Generation example in Java using iText Library

Continue Reading →

Fuzzy String Matching or Searching with Python Code

Hello everyone, I have been recently reading about Text Mining and Natural Language Processing (NP). So, I will be sharing a few articles on TextMining from now on. So, that you can have an interest in this beautiful field of Computer Science.

Prerequisites

In order to understand the main content of the article you need some prerequisites which are as follows :- 

• Familiar with Programming.
• Know at least one programming language.
• Basics of Python (Optional but Recommended)
• Have some prior exposure to Data Structures and algorithmic techniques like Backtracking, Dynamic Programming etc.
• Have some gray cells and have patience.
• Passion for Computer Science.

Let's Start,

---

The first question that should arise in your mind when you hear the term TextMining is What is TextMining and What does it do ? hence we will understand first what is Text or Data Mining. Lets proceed.

Text Mining or Data Mining

Text mining, also referred to as text data mining, roughly equivalent to text analytics, refers to the process of deriving high-quality information from text. High-quality information is typically derived through the devising of patterns and trends through means such as statistical pattern learning.

Text mining usually involves the process of structuring the input text (usually parsing, along with the addition of some derived linguistic features and the removal of others, and subsequent insertion into a database), deriving patterns within the structured data, and finally evaluation and interpretation of the output.

To explain it simply

Data Mining is a processing of locating or finding important expression, phrases or sentences or events from data or text which can be further processed to get more useful information. Even though data mining tries to collect information from data, its different from Information Retrieval, instead of the fact that Data Mining, Information Retrieval or Natural Language Processing are often connected together and misunderstood as one, I will explain how they are different some other time and not here. If you wanna develop an application based on Text or where you have to deal with large amount of data and you need an intelligent system which will classify the data and sorts them into different categories or do different processes then you need these concepts a lot.

Real life examples of Data Mining

1. Google Search : Whenever you starting writing a query it automatically suggests the possible search queries. How does it do ? They use these concept to derive the most probable search query.

2. Spell Correction : You might have seen that if you type wrong spelling's most search engines or word processors mark them with a red underline which means that you have a spelling error. MS Word or Android apps has automatic spell correction. They use these NLP and Text Mining concepts. See the image it will clear a lot of doubts. See how Google does spell correction and the search results are an example of the query I entered.

3. Amazon or Online Shopping Stores : Most of you must have done online shopping a lot. Whenever you visit a site for the first time and search for some specific product. You see some thing written as recommended for you. Next time when you visit that site you might be astonished to see that the products you see when you open the webpage are similar to what you had searched in your last visit but more refined. So, how does it work ? the earlier mentioned concepts are used for these. They collect your browsing history and process the data and finally show you the most recommended products.

There are thousands of examples just Google for it :P
I hope by now you have somewhat understood what is data or text mining. Now we will come to today's real discussion that is fuzzy string searching. So lets continue.

---

Today's Discussion

In this section we discuss about String matching or string similarity algorithms. We will discuss the following algorithms today.

1. Damerau-Lavenshtein Distance.
2. Levenshtein Distance.
3. Wagner-Fisher Algorithm.

Strings are among the most important elements of computer science. There are literally 100's of research papers on strings. String searching and matching is one of he most important part in Text Processing and text analysis, since all the data to intelligent systems are fed as string. Strings are nothing but a sequence of characters joined together.

Fuzzy String Searching or Fuzzy String Matching

Fuzzy string search algorithms are algorithms that are used to match either exactly or partially of one string with another string. So, what exactly does fuzzy mean ? 

Fuzzy by the word we can understand that elements that aren't clear or is like an illusion. Therefore, in short we say that when there is a set of n elements and another set of m elements and they both have partially same elements then we can say that the relation between them is fuzzy.

(Funny example Most women have a fuzzy thinking that their men are cheating on them but instead of taking it as fuzzy they take it for granted :P)

By Fuzzy string searching (also known as approximate string matching) we identify those strings which are similar to a set of other strings. A number of conclusions can be drawn from these like Similarity co-efficient, similar words etc, etc.

The problem of approximate string matching is typically divided into two sub-problems: finding approximate sub-string matches inside a given string and finding dictionary strings that match the pattern approximately.

Fuzzy search algorithms (also known as similarity search algorithms) serve as a base for spell-checkers and search engines like Google or Bing or Yahoo etc. For example, these algorithms are used to provide the "Did you mean ..." functionality that is very common.

Example :- 

If you ask a machine to find the similarity between two words and correct them if required, say, "Looks" and "Lookes", the machine will return true for the first string "Looks" as its correct and will return the corrected string as "Looks" from the erroneous string "Lookes".

Simple Formulation of Fuzzy String Problems :-

"Find in the text or dictionary of a finite size n for all the words that match a word given as input (or starts with the given word), taking into account m possible differences (errors)."

Fuzzy search algorithms are characterized by metric - a function of distance between two words, which provides a measure of their similarity. A strict mathematical definition of metric includes a requirement to meet triangle inequality (p - metric function, Z - a set of words):



LaTeX code for above equation.

p(x,y)  \leq p(x,k) + p(k,y), where,  (x,y,k)  \varepsilon  Z

What is Edit-Distance ?

Definition From Wikipedia

Edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other. Edit distances find applications in natural language processing, where automatic spelling correction can determine candidate corrections for a misspelled word by selecting words from a dictionary that have a low distance to the word in question.
Simply we can say that - The closeness of a match is measured in terms of the number of primitive operations necessary to convert the string into an exact match. This number is called the edit distance between the string and the pattern.

The primitive operations performed are, Insertion, Deletion, Substitution. Example :- 

1. Mad -- > Made, Insertion Operation Performed
2. Loooks -- > Looks, Deletion Operation Performed
3. Lick -- > Sick, Substitution Operation Performed

Now we will move to discuss the algorithms.

---

Damerau-Levenshtein Distance

Damerau-Levenshtein Distance is a distance (string metric) between two Strings, say String A and String B, which gives the minimum number of edit operations need to perform to transform String A to String B. Damerau's Algorithm can be used for spell correction with atmost 1 edit-distance.

There are four edit operations that can be performed with this algorithm. They are - 1. Insertion, 2. Deletion, 3. Substitution, and 4. Transposition. We have already seen the operation of the first three algorithms and so let me explain the last operation, that is transposition.

Transposition is the swapping of adjacent characters to bring them to a certain form.Example :-

String A := olko
String B := look

When the above two strings are feed to a machine that computes the Damerau-Lavenshtein Distance find that the edit distance is two. 

So how it operates ?
We have two string transpositions here :-

1.) olko -> loko 
2.) loko -> look

Hence we get the final result as :- look
And the number of edits performed is : 2

Please Note that Damerau-Levenshtein Distance doesn't follow the Triangle inequality. You can see that in the image below :-



"All Theory and No Code Makes Psycho a Dull guy"

I am giving the working function for now. You can see the Psuedo code on Wiki, its is well written.

Here's the code in Python. I would encourage you to write it by yourself too.

def damerau_levenshtein(s1, len_s1, s2, len_s2):
    """
    A function to calculate the Damerau-Levenshtein Distance.

    :param s1: Parent String
    :param len_s1: Length Of s1
    :param s2: pattern String
    :param len_s2: length of s2
    :rtype : int returns the damerau-levenshtein distance
    """

    d = {}
    len_s1 = len(s1)
    len_s2 = len(s2)
    for i in range(-1, len_s1 + 1):
        d[i, -1] = i + 1
    for j in range(-1, len_s2 + 1):
        d[-1, j] = j + 1

    for i in range(len_s1):
        for j in range(len_s2):
            if s1[i] == s2[j]:
                cost = 0
            else:
                cost = 1
                
            d[(i, j)] = min(
                d[i - 1, j] + 1,  # Deletion
                d[i, j - 1] + 1,  # Insertion
                d[i - 1, j - 1] + cost,  # Substitution
            )

            if i and j and s1[i] == s2[j - 1] and s1[i - 1] == s2[j]:
                d[i, j] = min(d[i, j], d[i - 2, j - 2] + cost)  # transposition
    return d[len_s1 - 1, len_s2 - 1]

You can get the complete source code here : https://github.com/AnimeshShaw/TextMin...nshtein.py
To see the Code in Execution :- http://code.hackerearth.com/0356acE
You can visualize how the steps or the algorithm works here : Click Me

Levenshtein Distance

Levenshtein distance is also a string metric calculate the edit-distance between two strings. They have found a lot of applications and in most of the real world systems an efficient and modified form of Levenshtein distance is used including various NLP toolkits like LingPipe or NLTK. or GATE. They use different data structures which reduces the time complexity.

The only difference between Lavenshtein and Damerau-Lavenshtein is that this algorithm doesn't supports transposition and we have only can perform only three operations namely, insertion, deletion and substitution.

Mathematically, it can be written as :-



LaTeX code for above equation

\qquad\operatorname{lev}_{s,t}(i,j) = \begin{cases}
  \max(i,j) \text{ if} \min(i,j)=0, \\
  \min \begin{cases}
          \operatorname{lev}_{s,t}(i-1,j) + 1 \\
          \operatorname{lev}_{s,t}(i,j-1) + 1 \\
          \operatorname{lev}_{s,t}(i-1,j-1) + 1_{(s_i \neq t_j)}
       \end{cases} \text{ else,}
\end{cases}

Another significant difference between Levenshtein Distance and Damerau-Levenshtein Distance is that the former satisfies the Triangle Inequality whereas the latter does not. It is visible from the image given below where the numbers represent the edit distance between two nodes :-

Okay, lets do some programming now. We can follow the above math relation an we can formulate a recursive solution :-

def recursivelevenshtein(s1, len_s1, s2, len_s2):
    """
    A function to calculate the Levenshtein Distance using recursion.

    :param s1: Parent String
    :param len_s1: Length Of s1
    :param s2: pattern String
    :param len_s2: length of s2
    :rtype : int returns the levenshtein distance
    """
    if len_s1 == 0:
        return len_s2
    if len_s2 == 0:
        return len_s1
    return min(
        recursivelevenshtein(s1, len_s1 - 1, s2, len_s2) + 1,  # Deletion
        recursivelevenshtein(s1, len_s1, s2, len_s2 - 1) + 1,  # Insertion
        recursivelevenshtein(s1, len_s1 - 1, s2, len_s2 - 1) + (s1[len_s1 - 1] != s2[len_s2 - 1])  # Substitution
    )

Full Source :- https://github.com/AnimeshShaw/TextMin...nshtein.py
See Execution :- http://code.hackerearth.com/4ac2f4u

(I haven't given the visualize python link here, but you can do it by yourself)

I hope you understood the process. But this backtracking technique is very very inefficient for larger strings. As the complexity is cubic. The space complexity is large. In order to improve the performance we use the Wagner-Fisher algorithm.

Wagner-Fisher Algorithm
Wagner-Fisher algorithm presents before us a Dynamic Programming approach to solve the Levenshtein Distance Problem in Quadratic time, O(m * n) where m and n are the length two input strings respectively.

Lets get to the code already :-

def wagner_fisher(s1, len_s1, s2, len_s2):
    """
    A function to calculate the Levenshtein Distance using
    Wagner-Fisher Algorithm.

    :param s1: Parent String
    :param len_s1: Length Of s1
    :param s2: pattern String
    :param len_s2: length of s2
    :rtype : int returns the levenshtein distance
    """
    d = {}

    #Make to use O(min(n,m)) space
    if len_s1 > len_s2:
        s1, s2 = s2, s1
        len_s1, len_s2 = len_s2, len_s1
    for i in range(-1, len_s1 + 1):
        d[(i, -1)] = i + 1
    for j in range(-1, len_s2 + 1):
        d[(-1, j)] = j + 1

    for i in range(len_s1):
        for j in range(len_s2):
            if s1[i] == s2[j]:
                d[i, j] = d[i - 1, j - 1]
            else:
                d[(i, j)] = min(
                    d[(i - 1, j)] + 1,  # deletion
                    d[(i, j - 1)] + 1,  # insertion
                    d[(i - 1, j - 1)] + 1,  # substitution
                )
    return d[len_s1 - 1, len_s2 - 1]

Full Source :- https://github.com/AnimeshShaw/TextMin...-Fisher.py
See Execution :- http://code.hackerearth.com/75dc9aJ

(I haven't given the visualize python link here, but you can do it by yourself)
Lets See how the lookup matrix is generated for the strings : "LAD" and "LLUDO"
Here's the final Matrix, just follow the algorithm step[ by step and you should get the following matrix, if you don't then you have made some mistakes.

+------+---+---+---+---+
| S1 → |   | L | A | D |
+------+---+---+---+---+
| S2 ↓ | 0 | 1 | 2 | 3 |
+------+---+---+---+---+
| L    | 1 | 0 | 1 | 2 |
+------+---+---+---+---+
| L    | 2 | 0 | 1 | 2 |
+------+---+---+---+---+
| U    | 3 | 1 | 1 | 2 |
+------+---+---+---+---+
| D    | 4 | 2 | 2 | 2 |
+------+---+---+---+---+
| O    | 5 | 3 | 3 | 3 |
+------+---+---+---+---+

The bottom-right element gives the Levenshtein edit distance. This process is better than recursive. Now my question to you is that, Can we improve further. Well I leave this to you. Find a method and write a code to find the edit distance using this algorithm which performs better than the present algorithm. Comment in the section below.

Using NLTK

If you're using NLTK the you can calculate it using :-

Conclusion

So, all folks we have come to an end of our first encounter with text Processing. If you made it till the end you probably have understood a nice algorithm. I will be posting more articles on these topics as soon as I have time. If you have some doubt then please ask but before that go through the tutorial properly and execute the codes by yourself and practice them by yourself.

References

http://en.wikipedia.org/wiki/Levenshtein_distance
http://en.wikipedia.org/wiki/Wagner-Fischer_algorithm
http://en.wikipedia.org/wiki/Fuzzy_string_searching
http://en.wikipedia.org/wiki/Damerau%E2%...n_distance
https://www8.cs.umu.se/kurser/TDBA77/VT0...NODE46.HTM

Online Tools Used

Online LaTeX : http://www.sciweavers.org/free-online-latex-equation-editor
Draw Diagrams : https://www.draw.io/
Text Table Generator : http://www.tablesgenerator.com/text_tables

Credits to @XxGreenLanternxX to header banner image.


Thank you,
Sincerely,
Psycho_Coder.

Related articles

• A Gentle Introduction to TextBlob for NLP
• String Permutations Algorithm with example code in C/C++
• Comma as Sequential-Evaluation Operator in C/C++
• Insertion Sort using Binary Search in Python
• Hash Algorithm Identifier | Identify CryptoHash Types
• Math Expression Parser in Java

Continue Reading →

Learning About the Stack Data Structure

Simple representation of a stack (Photo credit: Wikipedia)

Hello Everyone,

Today we will study about the data structure called Stack. But before roceeding with the tutorial I would like to read the following readers note.

Reader's Note :

• You must not be a novice at programming.
• You have read this thread : A Brief Introduction to Data Structures.
• Have patience and read till the end of this paper.
  

Now we are good to start, So, Let's Begin.

---

Stack : A stack is a particular kind of abstract data type or collection in which the principal (or only) operations on the collection are the addition of an entity to the collection. The operations that are performed on the the stack are push which means to insert an element at the top of the stack and pop which means to remove the top element from the stack.
Stack follows LIFO (Last In First Out) Principle, that is the element which is inserted into a collection last is taken out first from the collection as well.
The concept of stack data structure is from from development point of view and it has found numerous applications, include system level design and making efficient processes.

Applications of Stack
 
1. Data Parsing
2. Compiler Designing.
3. Recursion
4. Solving numerous Classical problems like Tower of Hanoi.
5. System Memory Management.
6. Reversing String.
7. Mathematical Expression evaluation. (Converting them from infix to postfix and then manipulating evaluating them)
8. Backtracking.
etc...
 
Stack as an Abstract datatype

StackADT {

push(item) : insert the item into the stack

pop() : removes the top element.

size() : Returns the size of the stack.

isEmpty() : checks whether the stack is empty or not.

isFull() : checks whether the stack is full or not.

}

Now let us understand the concept of stack better by taking an example :-

 

Suppose we consider an array of the following elements :-

5 <--- Top element

6

7

8

9

 

Now we push another number onto the stack, say 34, then our stack has the following structure :-

34 <--- Top element.

5

6

7

8

9

 

So it is evident that the most recently inserted items are push onto the top of the stack following the LIFO principle. Again we push another number into the stack, say 2, just following the above concept we have the following :-

2 <--- Top element.

34

5

6

7

8

9

 

We have understood the push operation and so lets see how does pop works. Lets pop once from the above array and the array becomes :-

34 <--- Top element.

5

6

7

8

9

 

As you can see the top element was poped from the stack and the next element that is 34 becomes the top element. Okay so lets pop two more elements and then the stack has the following structure :-

6 <--- Top element.

7

8

9

 

What happened above ?

 

First 34 is poped and then 5 becomes the top element and then another element i.e. 5 is poped and 6 becomes the top element.

I hope you have understood the concept of stack. Since we have understood the concept of stack and so lets write some code now. I will use Java to write the code. We create an interface to understand the concept of our ADT.

StackInterface.java

JStackArray.java

You can find the Java Generic Implementation of Stack Here

A Visual or Animated Representation of Stack can be found here

Okay, We are now ready to study some applications of Stack. So lets begin.

Example of an Application of Stack

String Reverse.

A Stack can be used to reverse a list, integer, string etc. Lets Look at the following example to understand the concept better :-

Suppose we have a string variable NAME and a string value of "Firun" assigned to it.

String NAME = "Firun";

Now since Stack follows the LIFO principle so if we insert every character from NAME into the stack then we will have 'n' as the top element. Then we can pop the elements we will have our Strings reversed. Look at the following working :-

1. Insert 'F' into Stack. We have

'F' <--- Top

2. Insert 'i' into Stack. We have

'i' <--- Top
'F'

3. Subsequently we insert the remaining characters as well and we get the following Stack structure.

'n' <--- Top
'u'
'r'
'i'
'F'

Now we pop all the elements from the stack and we have the following sequence :-

'u' <--- Top
'r'
'i'
'F'

We get 'n'

'r' <--- Top
'i'
'F'

We get 'u'. Also initially we had 'n' and so now we add 'u' to it and we get "nu". Proceeding in a similar way we get the final string as "nuriF".

I hope you understood the logic. So lets peep at the function code :-

private String reverseString(){
       String m="";
       for(int i=0;i<str.length();i++){
           stack.push(str.charAt(i));
       }
       for(int i=0;i<str.length();i++){
          m=m+stack.pop();
       }
       return m;
   }

Algorithm

PROCEDURE REVERSE_STRING(M) {
    INITIALISE LEN = LENGTH(M)
    FOR I TO LEN:
        STACK.PUSH(M[I])
    FOR I TO LEN:        
        N = N + STACK.POP()
    RETURN N
}

If you are able to make it to this end then it probably means that you have read the tutorial. I hope you enjoyed it. If you have any questions or doubts then feel free to ask.

Stacks are very useful and they reduce your workload, but it solely depends on the programmer how efficiently he uses these concepts. More applications of Stack like Conversion to different notations and Tower of Hanoi will be covered separately.

Feedback would be appreciated. Comment in the comment section below.

Thank you,

Sincerely,

Psycho_Coder.

Related articles

• Java Code to implement a Stack using Java Generics
• Visual Stack Application in Java
• Bag Data Structure Implementation in Java
• A Gentle Introduction to TextBlob for NLP
• String Permutations Algorithm with example code in C/C++

Continue Reading →

A Brief Introduction to Data Structures

Česky: (Photo credit: Wikipedia)

Hello Everyone,
 

So today I will discuss about Data structures and some other features related to it and its area of applications. Keeping the tradition in place as always, I would like you to read the following note before proceeding.

Readers Note:-

• In this part don't expect that this is the limit of data structures as the things I will mention here are the most basic elements
• My further tutorials on Data structure,if any, they will assume that you know at least know some programming, though the codes and explanation will be java based, but if you have a problem then post here.
• This part will be a theoretical one.
• Data Structures and algorithm's are two different aspects. So, don't think I will be teaching algorithms (To be true I am still not very proficient with principles of algorithm I need 5 more months to become able to teach others.)
• Lastly and most important point do read till the end of this tutorial.
  

Tutorial Objectives

• What are Data Structures ?
• Abstract Data type (ADT).
• Classification of Data Structures.
• Basic Operations on Data Structures.
• Relation between Data Structures and Algorithms
• Basic Data Structures :- Arrays, Stack, Queue, Lists, Trees and HashTable
• Application of Data Structures
• Conclusion.
• Recommended Reading.

Let's begin

---

What are Data Structures ?

Perhaps this the most important question in this particular tutorial. So let us define data structures.

A Data Structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. The data can be more than one variable. They also contain algorithms to process the data stored.

Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory, specified by an address. The implementation of a data structure usually requires writing a set of procedures that create and manipulate instances of that structure. The efficiency of a data structure cannot be analysed separately from those operations. A data structure may be defined indirectly by the operations that may be performed on it, and the mathematical properties of those operations (including space and time complexity.)

Abstract Data Type (ADT)

An abstract data type is a data type that satisfies two conditions:-

1. The representation, or definition, of the type and the operations are contained in a single syntactic unit.
2. The representation of objects of the type is hidden from the program units that use the type, so only direct operations possible on those objects are those provided in the type’s definition.
   

Another Definition :-

An abstract datatype is an encapsulation mechanism. In general it is composed of several components:-

• A data structure or structures (often called the sorts)
• A set of operations (called the methods or operations).
• A precise description of the types of the methods (called a signature).
• A precise set of rules about how it behaves (called the abstract specification or the axiomatic description).
• An implementation hidden from the programmer who uses the data type.
  

Example of an ADT (I assume that you know what array means)

Array ADT

create(A,N)                   :     creates an arrayAwith storage forNitems;
bool isEmpty()                : - Retrurns true if array is empty
bool isFull()                    : - Retrurns true if array is full
int length()                    : - Returns the length of the array
void add(int item,int pos) :– Adds the element at the given position
void del(int item)            : - Deletes the given item from the array.
void display()                 : - Prints the elements of array.

Note: Stack , Queue, Lists etc are all examples of ADT.

Classification of Data Structures

Data Structures are normally divided into two broad categories :-

Primitive Data Structures

The integers, real, logical data, character data, pointer and reference are primitive data structures. Data structures that normally are directly operated upon by machine-level instructions are known as primitive data structures.

Non-primitive Data Structures

These are more complex data structures. These data structures are derived from the primitive data structures. They stress on formation of sets of homogeneous and heterogeneous data elements.

Other classifications :-

Homogeneous and Heterogeneous Data Structures

Homogeneous data structure

Homogeneous data structures are those data structures that contain only similar type of data e.g. like a data structure containing only integral values or float values. The simplest example of such type of data structures is an Array.

Heterogeneous Data structure

Heterogeneous Data Structures are those data structures that contains a variety or dissimilar type of data, for e.g. a data structure that can contain various data of different data types like integer, float and character. The examples of such data structures include structures, class etc.

Static and Dynamic Data Structures

Static data structure

Static data structures are those data structures to which the memory is  assigned at the compile time, means the size of such data structures has to be predefined in the program and their memory can be increased or decreased during the execution. The simplest example of static data structure is an array.

Dynamic data structure

Dynamic Data Structures are those data structures to which memory  is assigned at the runtime or execution time and hence their size can be increased or decreased dynamically as per requirement of the program. The example of such data structures include class, linked lists etc.

Linear and Non-Linear Data Structures

Linear data structure

In linear data structures the data is kept in the sequential manner which means that the previous data has knowledge of next data or we can say that the data is interrelated. The example such data structures include arrays, linked lists etc.

Non-linear data-structure

Non-linear data structures does not maintain any kind of relationship among the data. The data is stored in non-sequential manner and examples of these types of data structures includes graphs, trees etc.


Basic Operations on Data Structure

Traversing : Accessing each record exactly once so that certain items in the record may be processed.(This accessing or processing is sometimes called 'visiting" the records.)

Searching : Finding the location of the record with a given key value, or finding the locations of all records, which satisfy one or more conditions.

Sorting : Arranging the data in some logical order.

Inserting : Adding new records to the structure.

Deleting : Removing a record from the structure.

Merging : Combining the data of two different sorted file into a single sorted file.

Sometimes two or more data structure of operations may be used to create another operation.

Relation between Data Structures and Algorithms

An algorithm in data structure are step-by-step instructions that a computer can read. It is used for programming software and applications based on calculations.

Algorithms and Data Structures are tightly wound together. Algorithm depends on data structures, if you change either of them, complexity will change considerably. They are not same, but are definitely two sides of the same coin. Selecting a good Data Structure is itself a path towards better algorithm.

Basic Data Structures :- Arrays, Stack, Queue, Lists, Trees and Graph.

Arrays

Arrays are a very simple data structure, and may be thought of as a list of a fixed length. Arrays are nice because of their simplicity, and are well suited for situations where the number of data items is known (or can be programmatically determined). Suppose you need a piece of code to calculate the average of several numbers. An array is a perfect data structure to hold the individual values, since they have no specific order, and the required computations do not require any special handling other than to iterate through all of the values. The other big strength of arrays is that they can be accessed randomly, by index. For instance, if you have an array containing a list of names of students seated in a classroom, where each seat is numbered 1 through n, then studentName(i) is a trivial way to read or store the name of the student in seat i.

An array might also be thought of as a pre-bound pad of paper. It has a fixed number of pages, each page holds information, and is in a predefined location that never changes.

Linked Lists

A linked list is a data structure that can hold an arbitrary number of data items, and can easily change size to add or remove items. A linked list, at its simplest, is a pointer to a data node. Each data node is then composed of data (possibly a record with several data values), and a pointer to the next node. At the end of the list, the pointer is set to null.

By nature of its design, a linked list is great for storing data when the number of items is either unknown, or subject to change. However, it provides no way to access an arbitrary item from the list, short of starting at the beginning and traversing through every node until you reach the one you want.

Stack

Stacks are, in a sense, the opposite of queues, in that they are described as "last in, first out". The classic example is the pile of plates at the local buffet. The workers can continue to add clean plates to the stack indefinitely, but every time, a visitor will remove from the stack the top plate, which is the last one that was added.

While it may seem that stacks are rarely implemented explicitly, a solid understanding of how they work, and how they are used implicitly, is worthwhile education. Those who have been programming for a while are intimately familiar with the way the stack is used every time a subroutine is called from within a program. Any parameters, and usually any local variables, are allocated out of space on the stack. Then, after the subroutine has finished, the local variables are removed, and the return address is "popped" from the stack, so that program execution can continue where it left off before calling the subroutine.

An understanding of what this implies becomes more important as functions call other functions, which in turn call other functions. Each function call increases the "nesting level" (the depth of function calls, if you will) of the execution, and uses increasingly more space on the stack. Of paramount importance is the case of a recursive function. When a recursive function continually calls itself, stack space is quickly used as the depth of recursion increases.

Queue

A queue is a data structure that is best described as "first in, first out". A real world example of a queue is people waiting in line at the bank. As each person enters the bank, he or she is "enqueued" at the back of the line. When a teller becomes available, they are "dequeued" at the front of the line.

Perhaps the most common use of a queue is to implement a Breadth First Search (BFS). BFS means to first explore all states that can be reached in one step, then all states that can be reached in two steps, etc. A queue assists in implementing this solution because it stores a list of all state spaces that have been visited.

A common type of problem might be the shortest path through a maze. Starting with the point of origin, determine all possible locations that can be reached in a single step, and add them to the queue. Then, dequeue a position, and find all locations that can be reached in one more step, and enqueue those new positions. Continue this process until either a path is found, or the queue is empty (in which case there is no path). Whenever a "shortest path" or "least number of moves" is requested, there is a good chance that a BFS, using a queue, will lead to a successful solution.

Tree

Trees are a data structure consisting of one or more data nodes. The first node is called the "root", and each node has zero or more "child nodes". The maximum number of children of a single node, and the maximum depth of children are limited in some cases by the exact type of data represented by the tree.

One of the most common examples of a tree is an XML document. The top-level document element is the root node, and each tag found within that is a child. Each of those tags may have children, and so on. At each node, the type of tag, and any attributes, constitutes the data for that node. In such a tree, the hierarchy and order of the nodes is well defined, and an important part of the data itself. Another good example of a tree is a written outline. The entire outline itself is a root node containing each of the top-level bullet points, each of which may contain one or more sub-bullets, and so on. The file storage system on most disks is also a tree structure.

HashTable

Hash tables are a unique data structure, and are typically used to implement a "dictionary" interface, whereby a set of keys each has an associated value. The key is used as an index to locate the associated values. This is not unlike a classical dictionary, where someone can find a definition (value) of a given word (key).

Unfortunately, not every type of data is quite as easy to sort as a simple dictionary word, and this is where the "hash" comes into play. Hashing is the process of generating a key value (in this case, typically a 32 or 64 bit integer) from a piece of data. This hash value then becomes a basis for organizing and sorting the data. The hash value might be the first n bits of data, the last n bits of data, a modulus of the value, or in some cases, a more complicated function. Using the hash value, different "hash buckets" can be set up to store data. If the hash values are distributed evenly (which is the case for an ideal hash algorithm), then the buckets will tend to fill up evenly, and in many cases, most buckets will have no more than one or only a few objects in them. This makes the search even faster.

A hash bucket containing more than one value is known as a "collision". The exact nature of collision handling is implementation specific, and is crucial to the performance of the hash table. One of the simplest methods is to implement a structure like a linked list at the hash bucket level, so that elements with the same hash value can be chained together at the proper location. Other, more complicated schemes may involve utilizing adjacent, unused locations in the table, or re-hashing the hash value to obtain a new value. As always, there are good and bad performance considerations (regarding time, size, and complexity) with any approach.

Most standard libraries, such the Java API, and the .NET framework, provide a Stack, Queue, Lists, HashTables class that provides the various data structure operations. Details on how to use the API will be discussed later.

Applications of Data Structure

Every application uses Data structure but it is upto how you can use data structure to create more efficient programs and applications. To name some are :-

• Compiler Design,
• Network flow model
• Operating System,
• Database Management System,
• Statistical analysis package,
• Numerical Analysis,
• Graphics,
• Artificial Intelligence,
• Simulation
  

Conclusion

To conclude I would say that data structures have a enormous application in the field of computing and it has touched us in every manner. I would recommend you to study data structure in great detail if you really want to be a good and efficient programmer. If you are interested  then I would ask you  to buy the books I have referred.

Recommended Reading

1. Art of Computer Programming, Volume 1: Fundamental Algorithms by Donald E. Knuth
2. Data Structures and Algorithm Analysis in C++, by Mark Allen Weiss
3. Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching by Robert Sedgewick
References Taken

1. Data Structures by Lipshutz and another one by Baluja.

2. Wikipedia.
3. http://www.topcoder.com/

Thank You for reading my tutorial and I hope that you enjoyed it.

Thank you,
Sincerely,
Psycho_Coder.

Related articles

• Java Code to implement a Stack using Java Generics
• Visual Stack Application in Java
• Recommended Books to become a Java Hero from Java Zero
• Math Expression Parser in Java
• Insertion Sort using Binary Search in Python
• Hash Algorithm Identifier | Identify CryptoHash Types

Continue Reading →