External Sort

 

I guess most of the people have implemented sorting algorithms like merge sort, quick sort, etc but they may not be aware of External Sort. So, What does this external sort mean?

In order to understand this concept, we will introduce a scenario. Suppose, we have to sort a file of size far larger than that of physical memory (RAM). To tackle this problem, firstly, increase the physical memory or secondly, try to introduce some other algorithm. Yes, second option is the better one but how?

This problem can be solved with this external merge sort algorithm. Let’s have a look of this algorithm.

This algorithm consists of two phases:

1) Creation of sorted sublists

2) Merging sublists to form a single file

Let’s start developing the foundation of the solution. Let the size of the main memory be ‘m’ buffers and that of file be ‘n’ such that n >> m. We can sort the file that has size less than or equal to the size of physical memory by making use of any known sorting algorithm. Here, sorting algorithms like merge sort cannot be used because such kind of sorting algorithm requires more memory for storing intermediate results.

Phase I:

Get the first m buffers (size of RAM) of the file into the main memory and sort using any internal sorting algorithm. Now, after sorting dump this onto the disk in a file called as sublist. Repeat this process until the whole file gets sorted into sublists. Obviously, we will get n/m no. of sublists. All the sublists will be nothing but sorted files of size equal to that of main memory.

Phase II:

So, we will get n/m = t (say) no. of sorted sublists.

Now, we have to merge these sorted sublists in order to create a single sorted file. One thing should be noted here, these sublists are not mutually sorted, don’t worry; you will understand the whole concept from the example.

Divide the main memory (logically) into (t+1) buffers as we have t sorted sublists and one extra buffer for storing the results of the merge operation. Now, the size of the buffer (s) will be equal to m/ (t+1). Read the s bytes from each sublists into the main memory and compare the top values from each buffer and put the lesser value into the output buffer and remove that value from its respective buffer. Fill the buffer when it becomes empty from its respective sublists. As soon as the output buffer gets full, dump it into an output file and this file will be the final sorted file that we wanted. All the dumps will be performed on the same output file in phase II.

For example,

Suppose we have a file containing the following nos.

1, 2, 3, 5, 4, 3, 5, 1, 3, 4, 5, 8, 3, 5, 1, 8, 3, 7, 4, 5 and we can store max. of 5 nos. at any instant of time in the main memory i.e. size of the main memory = 5 nos.

Now, we have to sort these nos. using External Sort mechanism.

Phase I:

Take first 5 nos. and put them in main memory, sort them and put them in a sublist.

Sublist 1: 1 2 3 4 5

Similarly, other sublists will be:

Sublist 2: 1 3 3 4 5

Sublist 3: 1 3 3 5 8

Sublist 4: 3 4 5 7 8

Phase II:

Now, we have 4 sublists, so 4 input plus 1 output buffers.

The working of this phase can be understood very easily from the above diagrams.

Step 1:

Initially, one no. from each sublist is loaded into physical memory (as each buffer can store only one no.) and the smallest no. is stored into the output buffer. This buffer is emptied/dumped into a file (output file).

Similarly,

Step 2:

Step 3:

 

Step 4:

Step 5:

In the similar fashion, we can go ahead until all the sublists become empty and at last the output file will contain sorted nos.

I hope, you can sort the files of huge sizes using external sorting algorithm that we have seen.

Please don’t forget to write the comments of appreciation or doubts.

TagMe

The current boom of the Web is associated with the revenues originated from online advertising. So, more emphasis nowadays, is being given to proper presentation of the Ads which then embodied into relevant pages. Almost all searching Giants like Google, Yahoo, Bing, etc. use Ads as the main source of revenues. Nowadays, advertisers put more efforts so as to make attractive Ads along with proper descriptions that would be quite helpful for making more profits both for advertiser as well as hosting websites.

So, it would be better if we can provide some more useful information about the words in the description. This is useful as far as users’ perspective is taken into consideration. Now, lets move to one of the most trending topic in the world of advertisement – “TagMe”.

What is TagMe ?

I guess, we all are familiar with tagging in FaceBook. In case of FB, we tag one of our friend’s name to a person’s face in the image. That is, we are adding more information about something. The same thing is related with advertisements. Given an Ad along with some description, we add some more relevant information about dominant words present in its description.

Consider, an Ad with some description as given below,

Auction for Bicycles Description Auction of second hand Bicycles & Two Wheelers in the campus of International Institute of Information Technology, Hyderabad on the basis of English Auction.

Suppose, I am interested in such kind of Ads. From the above description, I surely point out three points/things.
i) Bicycles & Two Wheelers
ii) English Auction
iii) International Institute of Information Technology, Hyderabad.

Out of these three points, I can understand the first point but what about the remaining points?
I don’t have any kind of information about what is English Auction?
and Where is International Institute of Information Technology, Hyderabad?
Till now, this was about the perspective of Ad interested user/s.

Now, we will see from the Advertiser’s perspective.

Every advertiser would want that his/her Ad should be visible to more and more users and the depth/meaning of the Ad must be conveyed to them clearly and easily.
Now, what steps should the advertisers take in order to give more clarity for points (ii) & (iii) ?

We can add more informative information about these points. That is when user hovers his/her cursor on the text, it should provide more precise information about the text into consideration. Yes, this approach is effective and more feasible to implement.

To understand this concept more precisely, just google tagme, open the first link and put some words into the textbox and then click Tagme. Now, observe the results carefully to understand the concept.

As this blog is for the developers and the people with strong technical skills in the field of computer science, we are going to develop some more efficient algorithm for TagMe concept with heavy discussions.

Implementation Perspective 

Certain important things must be pointed out in order to get clearer picture of what we have to implement.

i) From where we will get information about some words.
ii) Selection of particular words (keywords) for which more information has to be shown ( when hovered ).
Lets discuss these points one by one.

Point (i)

To resolve this problem, we must have certain DB from where we can get required information. But, the nature of this DB should be dynamic rather than static as information keeps changing every time. But the question is, which DB?

It would be better if we can get information from Wikipedia, which is stable, dynamic and more importantly it contains more Authentic Information. Yes, this matter is subjective and developer has full right to select its own repository.

Another important thing is that Wikipedia has provided very flexible API calls to fetch required data. Our aim is to show only overview that is the introductory part of Wikipedia page for the keyword.

Point (ii)

This is the most important phase of TagMe. In this phase, we have to make decision about selecting the keywords from the text. But how do we get to know that a particular word is a keyword and whether Wikipedia contains page for it or not ?

One way, I initially thought is that assign Parts of Speech (POS) tag to each of the words in the description of the Ad and extract all the noun words present in it. For these nouns, form the URL accordingly and get the information. This is very easy solution and it has some drawbacks. To understand this problem, consider our previous example of Auction Ad.

We tag all the words present in the description. Lets take into consideration the POS tags of International Institute of Information Technology, Hyderabad. Out of these words, Hyderabad is a noun. But the thing is that we must consider all these words as a single entity rather than individual. Now, looking into reverse way to this problem would give us the way to solve this ambiguity. Anyways, we have to get information from Wikipedia, so take into consideration those phrases (i.e. entities) that have a page ( as a title ) present in Wikipedia database. For doing so, create a file containing the title of all Wikipedia pages and note down the timestamp at which API call is made to fetch the titles. This timestamp will be useful when we want to update the titles of newly introduced pages into Wikipedia database through another API call to the File of Titles(FT).
Now, the whole problem is as follows:
i) Given an Ad description, search by taking into consideration ‘t’ words each time in FT for a match (entity).
ii) Form a URL for each of entity and get the required data from Wikipedia.

Data Structures

Since point(ii) form the base of TagMe, we will start with developing the same. The data structure for this phase should be Space and Search Efficient. So, I recommend Trie Data  Structure. Each node consists of a char space along with 26 pointers equals to no. of alphabets in English. If you don’t have any knowledge about Trie, search for it on the web, as we are not going into depth of this Data Structure. Trie contains all the titles present in FT. Two things we are concerned about using Trie are: i) The height and ii) The size of Main Memory.

The height of Trie will be equal to the no. of chars in the longest title in FT. Obviously, we require more Main memory for accommodating the whole Trie. But this Main Memory investment in one time as, it would be rare to have page title more than 30 chars. When you go into the depth of Trie construction for titles, you will get to know that it is also memory efficient Our concentration is about reducing search time for getting proper entities in the description of Ad. Trie is more efficient for searching. Also, we can make use of some compression technique in order to reduce the size of the titles. Now, take one or more words ( depending upon your algorithm design) from Ad description and search into Trie to check whether the group of selected words forms a title of Wikipedia page. As soon as we got a match, extract required introductory information using Wiki API.

Consider an example to have a broader sense of understanding about what we have explained till now.

PG on sharing basis for Rs. 8000 Description Paying Guests required on sharing basis near IIIT area Hyderabad for Rs. 8000/-.

Also Wikipedia contains pages for IIIT, Hyderabad, India, IIT, Delhi, etc. We have all these titles in our FT. From FT, we are going to create Trie for all these titles. The Trie structure will like this:

 

Now, we have consider the Ad description. Starting  with the word ‘Paying’, check it is there in the above structure or not. We will not find any words matched into this structure till IIIT. Note that this traversing not as easy  but the programmer has to take care of this. As soon as we find a match for IIIT, form a URL accordingly and extract the interested information. Continue this procedure till all the words in the description gets over. This was about what I thought of solving this problem, may be someone can have better solution than this.

I request all of you who are having better solution than this to share your valuable ideas here.

I hope you all eNjOy this post.

Please do write the comments/mails of appreciation.
Thanks a lot !!!!

Aria Subscription Billing System

Aria is a system founded by five Billing Experts, who have worked for LaserLink.net an internet service provider. Aria is basically a billing system which generates bill based upon the usage and the charges. For instance, mobile service providers may use Aria for generating bills of their subscribers based upon the usage of the services. Service Provider registers each subscriber of a service into Aria system with some information like Name, Address, Plans, Bill payment type, etc. Also the information like cost per unit of usage, required for generating the bill has to be provided at the time of user registration.

Aria information can be accessed through the website() or we can access it making http connections or REST calls. Some companies use Aria as a third party bill generating system use it by making REST calls.

For making these calls we have to provide some authentication information like Auth Key and Client No. in the url itself. Also with this information, we have to embed parameters, corresponding to the function that is called. Aria system provided some useful rest calls to access its information. There is proper documentation of these rest calls  here .

For example,

URL Formation:

https://secure.future.stage.ariasystems.net/api/AriaQuery/objects.php?rest_call=get_acct_details_all&client_no=Client_No&auth_key=Auth_key&acct_no=Account_No&output_format=json

Here, https://secure.future.stage.ariasystems.net/api/AriaQuery/objects.php? Is the Base Url and we are making use of the function get_acct_details_all which requires three parameters:

1. client_no
2. auth_key
3. acct_no

Out of these parameters first two are necessary for making any Aria call. Each key-value pair in the url is separated by the delimiter '&'. Aria returns output in the form of Xml or as json.

ARIA Functions:

There are no. of various API functions provided by Aria. These functions are divided into some categories depending upon the functionality they perform. The important thing here is to notice that all functions except the functions with query as a parameter require, same base url.

Functions without query as a parameter:

Base Url:

https://secure.future.stage.ariasystems.net/api/ws/api_ws_class_dispatcher.php?

Functions with Query as a parameter:

The above functions take query string as a parameter-

1. get_account_details( username, password, limit, offset, query_string)
2. get_account_status_history(username, password, limit,offset, query_string)
3. get_account_plan _history( username, password, limit, offset, query_string)
4. get_payment_details( username, password, limit, offset, query_string)
5. get_order_details( username, password, limit, offset, query_string)
6. get_invoice_information( username, password, limit, offset, query_string)
7. get_transaction_information( username, password, limit, offset, query_string)
8. get_transaction_information( username, password, limit, offset, query_string)
9. get_coupon_history (client_no, auth_key, limit, offset, query_string)

where,

limit - The maximum number of objects that should be returned by this call.

offset - The number of records to skip. Note that both "0" and NULL will cause the interface not to skip any records.

query_string - The criteria which all returned objects must match. Different objects have a different .

Base Url:  https://secure.future.stage.ariasystems.net/api/AriaQuery/objects.php?

Some information cannot be directly accessed by these calls, instead we have to write a query along with the function calls. Suppose we have to get information about all the accounts present under a client. For doing this no function is provided by Aria. So, we have to write a query “acct_no != 0” in encoded format like acct_no%20!%3D%200%3E.

For example,

https://secure.future.stage.ariasystems.net/api/AriaQuery/objects.php?rest_call=get_account_details_all&client_no=Client_No&auth_key=Auth_key&acct_no=Account_No&output_format=json&query_string=acct_no%20!%3D%200%3E

Here we have used acct_no as a condition parameter. Aria API Documentation has apparently given which parameters we can specify in the query for a particular function.

Instead of writing the code for accessing information, we can use Postman – Rest Client from the google chrome store which can provide the data in Xml or in Json format.

Based on the previous discussion, we have written the code to get data from Aria. Where we are getting data in the form Json string and then converting it into Json Object as shown.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.net.URL;
import java.net.URLConnection;
import java.util.ArrayList;
import com.google.gson.JsonObject;
import com.google.gson.JsonParser;


public JsonObject getAriaResponse(String ariaUri,String ariaFuncString,String queryString)
{
 String responseStr;
 String clientNo = "Enter Client No";
 String authKey = "Enter Auth Key";
 JsonParser jParser = new JsonParser();
 JsonObject obj = new JsonObject();
 String UrlStr;
 
 try
 {         
  if(queryString != null)
   UrlStr = ariaUri + "rest_call=" + ariaFuncString+"&client_no="+clientNo+"&auth_key="+authKey+"&query_string="+queryString+"&output_format=json";
  else
   UrlStr = ariaUri + "rest_call=" + ariaFuncString+"&client_no="+clientNo+"&auth_key="+authKey+"&output_format=json";   
  
  System.out.println("URI: "+UrlStr);
  URL url = new URL(UrlStr);
  URLConnection urlc = url.openConnection();
  urlc.setDoOutput(true);
  urlc.setAllowUserInteraction(false);
  PrintStream ps = new PrintStream(urlc.getOutputStream());
  ps.close();
  BufferedReader br = new BufferedReader(new InputStreamReader(urlc.getInputStream()));  
  responseStr = br.readLine();
  obj = jParser.parse(responseStr).getAsJsonObject(); 
 }
 catch(Exception e)
 {
  e.printStackTrace();
 }
 return obj;
}

SAX Parser

SAX is the Simple API for XML originally a Java API. SAX parser can be used for parsing XML documents in an efficient and well mannered way. SAX parser use callback function (org.xml.sax.helpers.DefaultHandler) to inform clients of the XML document structure. In case of Java, we can extend DeafultHanlder and override few methods to achieve XML parsing.

There are some methods or functions provided:

1) startDocument() : This function executes at the start of the document.

2) startElement() : This function executes at the start of each and every tag where we can set some boolean variables to true.

3) endDocument() : This function executes at the end of the document.

4) endElement() : This function executes at the end of each and every tag where we can set some boolean variables to false.

5) characters() : It is an important function as it displays the text between the start tag and its corresponding end tag.

Now, consider that we have to parse the above xml file.

<company>

           <employee>

                          <name>Azim</name>

                          <id>201205556</id>

                          <degree>M.Tech</degree>

                          <history>

                                      <name>Progress Software</name>

                          </history>

           </employee>

           <employee>

                         <name>Aditya</name>

                         <id>AK47</id>

                         <degree>B.Tech</degree>

                         <history>

                                     <name>Synechron</name>

                         </history>

            </employee>

            <employee>

                          <name>Abdul</name>

                          <id>40040</id>

                          <degree>B.E</degree>

                          <history>

                                     <name>Cognizant</name>

                                     <name>Wipro</name>

                          </history>

            </employee>

</company>

The following example demonstrates the use of DefaultHandler and various functionalities provided in Java.

import java.io.File;
import java.io.OutputStreamWriter;
import java.io.Writer;
import javax.xml.parsers.SAXParser;
import javax.xml.parsers.SAXParserFactory;
import org.xml.sax.Attributes;
import org.xml.sax.SAXException;
import org.xml.sax.helpers.DefaultHandler;



public class SAX extends DefaultHandler
{
 public static String inputXMLFile = "/home/star/workspace1/PracticeSession/sample.xml";
 public static Writer out;    
 public static boolean empFlag,nameFlag,idFlag,historyFlag,degFlag,histNameFlag;
 
 public static void main (String argv []) 
 {       
  empFlag = nameFlag = idFlag = historyFlag = degFlag = histNameFlag =false;
  SAXParserFactory factory = SAXParserFactory.newInstance();        
  try 
  {
   //Setting up the output stream - in this case System.out with UTF8 encoding
   out = new OutputStreamWriter(System.out, "UTF8");
   //Getting a parser from the factory
   SAXParser saxParser = factory.newSAXParser();
   //Parsing the XML document using the parser
   saxParser.parse( new File(inputXMLFile), new SAX());
  } 
  catch (Throwable throwable) 
  { 
   throwable.printStackTrace ();
  }
 } 
 
 public void startDocument() throws SAXException
 {
  System.out.println("Document Parsing Started:");
 }

 public void endDocument()throws SAXException
 {     
  System.out.println("Document Parsing Completed Successfully:");
 }

 public void startElement(String namespaceURI, String localName, String qName, Attributes atts)throws SAXException
 {  
  if(qName.equalsIgnoreCase("employee"))
   empFlag = true;
  else if(qName.equalsIgnoreCase("name") && historyFlag)   // for  tag in 
   histNameFlag = true;
  else if(qName.equalsIgnoreCase("name"))   // for only  tag
   nameFlag = true;
  else if(qName.equalsIgnoreCase("id"))
   idFlag = true;
  else if(qName.equalsIgnoreCase("history"))
   historyFlag = true;
 }

 public void endElement(String namespaceURI, String localName, String qName) throws SAXException
 {
  if(qName.equalsIgnoreCase("employee"))
   empFlag = false;
  else if(qName.equalsIgnoreCase("name") && historyFlag)
   histNameFlag = false;
  else if(qName.equalsIgnoreCase("name"))
   nameFlag = false;
  else if(qName.equalsIgnoreCase("id"))
   idFlag = false;
  else if(qName.equalsIgnoreCase("history"))
   historyFlag = false;
 }

 public void characters(char buffer [], int offset, int length) throws SAXException
 {
  String str = new String(buffer, offset, length);
  if(nameFlag && !historyFlag)
  {
   System.out.println("Employee Details:");
   System.out.println("Name: "+ str);
  }
  else if(histNameFlag)
   System.out.println("Previous Company Name: "+ str);
  else if(idFlag)
   System.out.println("Id: "+ str);
  else if(degFlag)
   System.out.println("Degree: "+ str);
 }
};

Output:
Document Parsing Started:
Employee Details:
Name: Azim
Id: 201205556
Previous Company Name: Progress Software
Employee Details:
Name: Aditya
Id: AK47
Previous Company Name: Synechron
Employee Details:
Name: Abdul
Id: 40040
Previous Company Name: Cognizant
Previous Company Name: Wipro
Document Parsing Completed Successfully: