MapReduce and GFS

Articles about other famous Google technologies:

• The Google File System
• MapReduce: Simplifed Data Processing on Large Clusters

See also:

• Bigtable: Distributed Storage System
• MapReduce @ Wikipedia
• Google File System @ Wikipedia
  

Suffix Trees: Java Ukkonen's Algorithm

Suffix Tree is a data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many important string operations. Details...

Ukkonen's algorithm begins with an implicit suffix tree containing the first character of the string. Then it steps through the string adding successive characters until the tree is complete. This order addition of characters gives Ukkonen's algorithm its "on-line" property; earlier algorithms proceeded backward from the last character. The implementation of this algorithm requires O(n) (linear time).

Check Suffix Tree Java Source Code
This is a Java-port of Mark Nelson's C++ implementation of Ukkonen's algorithm.

Test run and validation is moved to SuffixTreeTest JUnit Test Case.
Could be tested with Maven or from IDE.

mvn test
...
-------------------------------------------------------
T E S T S
-------------------------------------------------------
Running com.blogspot.illyakeeplearning.suffixtree.SuffixTreeTest
Start End   Suf   First Last  String
0     5     0     1     1     a
0     3     5     0     1     ca
0     7     -1    4     4     o
3     1     -1    2     4     cao
3     4     -1    4     4     o
5     2     -1    2     4     cao
5     6     -1    4     4     o
Suffix : acao
comparing: acao to acao
Suffix : ao
comparing: ao to ao
Suffix : cacao
comparing: cacao to cacao
Suffix : cao
comparing: cao to cao
Suffix : o
comparing: o to o
All Suffixes present!
Leaf count : 5 OK
Branch count : 7 OK
Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.032 sec

Results :

Tests run: 1, Failures: 0, Errors: 0, Skipped: 0

Future plans:

• refactor to have less global variables
• reuse java hash

References:

• Mark Nelson. Fast String Searching With Suffix Trees
• Esko Ukkonen. On–line construction of suffix trees
• Java String Internals

MySQL InnoDB Tuning

Here I've collected information about MySQL InnoDB Tuning:

• MySQL 5.0 Reference Manual :: 13 Storage Engines :: 13.2 The InnoDB Storage Engine :: 13.2.13 InnoDB Performance Tuning and Troubleshooting :: 13.2.13.1 InnoDB Performance Tuning Tips
• MySQL 5.0 Reference Manual :: 13 Storage Engines :: 13.2 The InnoDB Storage Engine :: 13.2.13 InnoDB Performance Tuning and Troubleshooting
• Innodb Performance Optimization Basics
• MySQL/Innodb performance optimization

Some my advices:

• After any configuration change do server restart
• After any server restart do SHOW INNODB STATUS sql command to check that InnoDB engine is up
  

Formal Grammars and Tools for Java

A grammar is formally defined as the ordered quad-tuple (N,Σ,P,S),
where:

• a finite set N of nonterminal symbols;
• a finite set Σ of terminal symbols that is disjoint from N;
• a finite set P of production rules;
• a distinguished symbol S from set N that is the start symbol.

Chomsky hierarchy of classes of formal grammars:

• type 0 - unrestricted grammars - include all formal grammars;
• type 1 - context-sensitive grammars - generate the context-sensitive languages;
• type 2 - context-free grammars - generate the context-free languages. Context free languages are the theoretical basis for the syntax of most programming languages;
• type 3 - regular grammars - generate the regular languages. Regular languages are commonly used to define search patterns and the lexical structure of programming languages.

In computer science, Extended Backus–Naur Form (EBNF) is a metasyntax notation used to express context-free grammars: that is, a formal way to describe computer programming languages and other formal languages. It is an extension of the basic Backus–Naur Form (BNF) metasyntax notation.

Compiler of computer programming languages consists of:

• parsing:
  • lexical analysis - produces tokens / lexemes;
  • syntactic analysis - produces parse tree or abstract syntax tree (AST);
• optimizer (optional);
• code generator.

Types of parsers:

• Top-down parsing
• Bottom-up parsing

Sample:

• grammar:
  S ::= Ax
  A ::= a
  A ::= b
  
  
• input sequence:
  ax
  
  
• Top-down parsing:
  S → Ax → ax
  
  
• Bottom-up parsing:
  ax → Ax → S
  

Top-down parsers:

• LL parser (Left-to-right, Leftmost derivation)

Bottom-up parsers:

• LR parser (Left-to-right, Rightmost derivation)
• SLR parser (Simple LR parser)
• LALR parser (lookahead LR parser)

In good review of Lex and Yacc for Java next tools were selected:

• ANTLR
• JavaCC
• SableCC

I think that ANTLR is one of the best tools because:

• it has a lot of features
• it has nice GUI - ANTLRWorks
• there are a lot of sample grammars
• there is a book - The Definitive ANTLR Reference: Building Domain-Specific Languages (DSL)
  

Screens of ANTLR GUI:

Post Archives to Your Blog

If you need to post an archive (source codes, binaries, etc) to your blog then check next advices:

• usually you are not able to post an archive to your blog
• the only thing you can do is to have a link to external location
• so you need to have a public web site to store archives
  
  • check GeoCities
    
• or you could share archives with some collaboration tools
  
  • check box.net

And you can add links like next:

• Paging Demo Binary and Source Code
• Paging AJAX Binary and Source Code

Java String Internals

General info about Java Strings could be found in API Doc.
Strings are immutable. So they can't be changed.

Strings store value internally in char array and have offset of the first character and characters count.

/** The value is used for character storage. */
private final char value[];
  
/** The offset is the first index of the storage that is used. */
private final int offset;
  
/** The count is the number of characters in the String. */
private final int count;

Example of initialization of empty String:

public String() {
    this.offset = 0;
    this.count = 0;
    this.value = new char[0];
}

Strings could share the same character array. Check constructor and substring code:

// Package private constructor which shares value array for speed.
String(int offset, int count, char value[]) {
    this.value = value;
    this.offset = offset;
    this.count = count;
}
  
public String substring(int beginIndex, int endIndex) {
    ...
    return ((beginIndex == 0) && (endIndex == count)) ? this :
        new String(offset + beginIndex, endIndex - beginIndex, value);
}

Sample:

String str = "Hello World";
String substr = str.substring(6, 11);

Low level system implementation of String class follows Flyweight Design Pattern

/**
 * Returns a canonical representation for the string object.
 *
 * @return  a string that has the same contents as this string, but is
 *          guaranteed to be from a pool of unique strings.
 */
public native String intern();

Sample:

String world = "World";
String str = "Hello World";
  
String substr1 = str.substring(6, 11);
String substr2 = str.substring(6, 11).intern();

Bigtable: Distributed Storage System

Here I've tried to collect information about Bigtable:

• Google Research Publication: BigTable
• Bigtable: A Distributed Storage System for Structured Data
• BigTable - Wikipedia, the free encyclopedia
• Google's BigTable
• Back to the Future for Data Storage
• The Python Datastore API
• Videos