Sunday, October 6, 2013

C++ - Bitap algorithm for Levenshtein distance calculation

In information theory and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertion, deletion, substitution) required to change one word into the other.

The bitap algorithm (also known as the shift-orshift-and or Baeza-Yates–Gonnet algorithm) is an approximate string matching algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given pattern, where approximate equality is defined in terms of Levenshtein distance — if the substring and pattern are within a given distance k of each other, then the algorithm considers them equal.


C++ implementation of bitap algorithm is given below:



#include 
#include 

using namespace std;

#define Diff_Timeout    1.0f
#define Diff_EditCost   4
#define Match_Threshold   0.5f
#define Match_Distance   100
#define Patch_DeleteThreshold 0.5f
#define Patch_Margin    4
#define Match_MaxBits   32

int match_bitap(const wstring &text, const wstring &pattern, int loc) 
{
 if (!(Match_MaxBits == 0 || pattern.length() <= Match_MaxBits)) 
 {
  throw _T("Pattern too long for this application.");
 }

 // Initialize the alphabet.
 map  s = match_alphabet(pattern);

 // Highest score beyond which we give up.
 double score_threshold = Match_Threshold;
 // Is there a nearby exact match? (speedup)
 int best_loc = text.find(pattern, loc);
 
 if (best_loc != -1) 
 {
  score_threshold = min(match_bitapScore(0, best_loc, loc, pattern), score_threshold);
  // What about in the other direction? (speedup)
  best_loc = text.rfind(pattern, loc + pattern.length());
  if (best_loc != -1) {
   score_threshold = min(match_bitapScore(0, best_loc, loc, pattern), score_threshold);
  }
 }

 // Initialize the bit arrays.
 int matchmask = 1 << (pattern.length() - 1);
 best_loc = -1;

 int bin_min, bin_mid;
 int bin_max = pattern.length() + text.length();
 int *rd;
 int *last_rd = NULL;
 
 for (int d = 0; d < pattern.length(); d++) 
 {
  // Scan for the best match; each iteration allows for one more error.
  // Run a binary search to determine how far from 'loc' we can stray at
  // this error level.
  bin_min = 0;
  bin_mid = bin_max;
  
  while (bin_min < bin_mid) 
  {
   if (match_bitapScore(d, loc + bin_mid, loc, pattern) <= score_threshold) 
   {
     bin_min = bin_mid;
   } 
   else 
   {
    bin_max = bin_mid;
   }
   
   bin_mid = (bin_max - bin_min) / 2 + bin_min;
  }
  
  // Use the result from this iteration as the maximum for the next.
  bin_max = bin_mid;
  int start = max(1, loc - bin_mid + 1);
  int finish = min(loc + bin_mid, text.length()) + pattern.length();

  rd = new int[finish + 2];
  rd[finish + 1] = (1 << d) - 1;
  
  for (int j = finish; j >= start; j--) 
  {
   int charMatch;
   
   if (text.length() <= j - 1) 
   {
    // Out of range.
    charMatch = 0;
   } 
   else 
   {
    charMatch = s[text[j - 1]];
   }

   if (d == 0) 
   {
    // First pass: exact match.
    rd[j] = ((rd[j + 1] << 1) | 1) & charMatch;
   } 
   else 
   {
    // Subsequent passes: fuzzy match.
    rd[j] = ((rd[j + 1] << 1) | 1) & charMatch
     | (((last_rd[j + 1] | last_rd[j]) << 1) | 1)
     | last_rd[j + 1];
   }
   
   if ((rd[j] & matchmask) != 0) 
   {
    double score = match_bitapScore(d, j - 1, loc, pattern);
    // This match will almost certainly be better than any existing
    // match.  But check anyway.
    if (score <= score_threshold) 
    {
     // Told you so.
     score_threshold = score;
     best_loc = j - 1;
     if (best_loc > loc) 
     {
      // When passing loc, don't exceed our current distance from loc.
      start = max(1, 2 * loc - best_loc);
     } 
     else 
     {
      // Already passed loc, downhill from here on in.
      break;
     }
    }
   }
  }

  if (match_bitapScore(d + 1, loc, loc, pattern) > score_threshold) 
  {
   // No hope for a (better) match at greater error levels.
   break;
  }
  
  delete [] last_rd;
  last_rd = rd;
 }

 delete [] last_rd;
 delete [] rd;
 return best_loc;
}


double match_bitapScore(int e, int x, int loc, const wstring &pattern) 
{
 const float accuracy = static_cast (e) / pattern.length();
 const int proximity = abs(loc - x);
 
 if (Match_Distance == 0) 
 {
  // Dodge divide by zero error.
  return proximity == 0 ? accuracy : 1.0;
 }
 
 return accuracy + (proximity / static_cast (Match_Distance));
}


map  match_alphabet(const wstring &pattern) 
{
 map  s;
 int i;
 
 for (i = 0; i < pattern.length(); i++) 
 {
  TCHAR c = pattern[i];
  s[c] = 0;
 }
 
 for (i = 0; i < pattern.length(); i++) 
 {
  TCHAR c = pattern[i];
  s[c] = (s[c] | (1 << (pattern.length() - i - 1)));
 }

 return s;
}

The call to procedure is as follows:

int res = match_bitap(stringOnestringTwo, 0);

where stringOne and stringTwo are strings whose match (Levenshtein distance) is to be determined, and 0 is location in stringOne where matching procedure should start. Return value is Levenshtein distance, as described above.

Thursday, June 20, 2013

HTML - Boxes around text within HTML table cell


If you want to have boxes only around some text within larger HTML container (td, div), use following code:


<span style="display:inline-block;border:1px solid #000;">
Your text goes here...
</span>


If you apply code to text within <td> element of a table, you'll get result like this:



Thursday, February 21, 2013

Android App - Zoromatic ScreenLock

Zoromatic ScreenLock is standalone Android application which allows user to lock device's screen, with one single click. This is not a widget, so it does not resides in memory, it turns itself off after lock.



Settings screen allows user to provide administration rights to the application:



Before uninstall, ScreenLock Admin rights should be disabled in Settings.

ScreenLock works on Android 2.2 or newer. The newest version can be downloaded from here.

Friday, February 8, 2013

Android App - Zoromatic Widgets

Zoromatic Widgets are set of multifunctional widgets for Android 2.2 and higher. To add any of available widgets to your home screen, long tap the screen, select Widgets from menu, and then select Zoromatic Widgets.

Available widgets:
  • Weather and Clock widget
  • Battery Status
  • Power Widget (multiple widgets)
  • Toggle WiFi
  • Toggle Mobile Data
  • Toggle Ringer
  • Toggle GPS
  • Toggle Bluetooth
  • Toggle Airplane Mode
  • Toggle NFC
  • Toggle Auto Sync
  • Set Screen Brightness



Weather and Clock widget is configurable, each widget has its own settings. Some of available custom options for clock piece of main widget are:
  • Clock color
  • Clock font
  • Clock skin
  • Widget transparency
  • Date format

Weather settings include:
  • Temperature scale (Celsius, Fahrenheit)
  • Custom weather icons
  • Location settings (Current location, using GPS, and custom location)
  • Refresh interval (30 minutes to 6 hours)
  • Use WiFi only for scheduled refresh

                     
There is weather forecast available for each weather widget, for selected locations



Application also provides battery status notification in status bar, theme and language selection:



Widgets work on Android 2.2 and newer. The newest version can be downloaded here.

Windows App - MiniPad - Syntax Highlighting Text and Source Code Editor

MiniPad is fully equipped text and source code editor, with syntax highlighting feature. It offers following main functionalities:

  • Work with both ASCII and Unicode files;
  • Syntax highlighting support for more than 32 groups of file types, with over 100 types supported in total;
  • Basic editing options (cut, copy, paste, delete, drag and drop blocks);
  • Navigation options (find, replace, bookmarks, go to line);
  • Formatting text (font, text and background colors, lower-upper case transitions);
  • Column selection (experimental);
  • Full screen view;
  • Switch between multiple documents or tabbed interface;
  • Application themes (from Windows 2000 to Office 2007);




Works on Windows XP and higher.

The application is single executable and can be downloaded here.








Thursday, January 17, 2013

CSS - Horizontal menu, show sub-menus on hover, autohide when hover is moved


Following example how to create navigation horizontal menu, with following features:

- menu items have horizontal sub-menus with one row
- menu item for current page is highlighted
- sub-menu for current page is always shown, except when overlapped with sub-menu from hovered menu item
- sub-menus for hovered items are automatically hidden when hover is moved to another item, except for sub-menu for current page


Picture 1

Full CSS code is given below:

html  
{
   min-width: 600px; 
}

body, div, td, th, h2, h3, h4 
{ 
   font-family: verdana,sans-serif;
 font-size: x-small;
 voice-family: "\"}\"";
 voice-family: inherit;
 font-size: small;
 color: #030303; 
}

div
{
 border: none;
 border: 0px;
 margin: 0px;
 padding: 0px;
 font-family: verdana,geneva,arial,helvetica,sans-serif;
 font-size: 14px;
 font-weight: normal;
 color: #030303;
}

p.note 
{
 background: #E0E0E0;
 padding: 4px;
 font-family: tahoma;
 font-size: 85%;
 line-height: 130%;
 margin-top: 0;
}

#contents 
{
 border: 2px solid #000000;
 padding: 15px;
 background: #D0D0D0;
 min-height: 300px;
}

#ulNav 
{
 position: relative;
 display: block;
 height: 28px;
 width: 100%;
 background: #224D6F;
 /*background: url(../images/menu-bg.gif) top left repeat-x;*/
 margin: 0;
 padding: 0;
}

#ulNav li ul
{
 display: block; 
}

#ulNav a 
{
 text-decoration: none;
}

#ulNav li 
{ 
 margin: 0;
 float: left;
 display: block;
 padding-right: 15px;
 text-align: center;
 line-height: 28px;
}

#ulNav li ul 
{
 display: none;
}

#ulNav li.off ul, #ulNav li.on ul  
{ 
 position: absolute;
 top: 25px;
 left: 0; 
 background: #224D6F;
 /*background:url(../images/menu-bg.gif) top left repeat-x;*/
 height: 28px;
 width: 100%;
 margin: 0;
 padding: 0;  
}

#ulNav li.on ul 
{
 background: #224D6F;
 /*background:url(../images/menu-bg.gif) top left repeat-x;*/
 width: 100%;
 margin: 0;
 padding: 0;  
}

#ulNav li.on:hover ul, #ulNav li.over ul /*for ie*/
{  
 background: #224D6F;
 /*background:url(../images/menu-bg.gif) top left repeat-x;*/
 width: 100%;
}

#ulNav li a 
{
 color: #FFFFFF;
 font-weight: bold; 
 display: block;
 width: 93px;
 padding: 0;  
}

#ulNav li.on a 
{
 color: #FF6A00;
}

#ulNav li.on ul a, #ulNav li.off ul a 
{
 border: 0;
 float: left; /*ie doesn't inherit the float*/
 color: #FF6A00;
 width: 100%;
 margin: 0;
 padding: 0; 
}

#ulNav li.on:hover ul a, #ulNav li.over ul li a /*for ie - the specificity is necessary*/
{ 
 background: #224D6F;
 /*background: url(../images/menu-bg.gif) top left repeat-x;*/
}

#ulNav li.on ul 
{
 display: block;
}

#ulNav li.off:hover ul, #ulNav li.over ul 
{
 display: block;
 z-index: 6000;
}

#ulNav li.off a:hover, #ulNav li.on a:hover 
{ 
 color: #FF6A00;
}

#ulNav li span 
{
 position: absolute;
}

#liSubnav a 
{
 display: block;
 position: relative;
 height: 28px;
}

#ulNav li.off ul a, #ulNav li.on ul a 
{
 display: block;
 background: #224D6F;
 /*background: url(../images/menu-bg.gif) top left repeat-x;*/
 color: #FFFFFF;
 font-family: arial, verdana, sans-serif;
 font-size: small;
 margin: 0;
 padding: 0;
 padding-left: 10px;
}  

#ulNav li.on ul a 
{
 background: #224D6F;
 /*background: url(../images/menu-bg.gif) top left repeat-x;*/
 margin: 0;
 padding: 0;
 padding-left: 10px;
}
  

Apply CSS in your web page code, for all pages. For current page, set href="#" id="current". For given snapshots, HTML code looks like this:

<div>
    <ul id="ulNav">
     <li id="liSubnav" class="off"><a href="Home.aspx">Home</a></li>
     <li id="liSubnav" class="off"><a href="Services.aspx">Services</a>
        <ul>
     <li><a href="#">Finance</a></li>
       <li><a href="#">Weather</a></li>
       <li><a href="#">Shopping</a></li>
      </ul>
   </li>
     <li id="liSubnav" class="on"><a href="#" id="current">Community</a>
        <ul>
       <li><a href="#">Blog</a></li>
       <li><a href="#">Chat</a></li>
       <li><a href="#">Forum</a></li>    
      </ul>
   </li>
     <li id="liSubnav" class="off"><a href="About.aspx">About</a>
        <ul>
       <li><a href="#">Company</a></li>
       <li><a href="#">People</a></li>
       <li><a href="#">Careers</a></li>
      </ul>
     </li>
     <li id="liSubnav" class="off"><a href="Contact.aspx">Contact</a></li>
    </ul>
 </div>

If you like to have modern look, with gradient menu items, use background image, instead of simple color. Image in Picture 2 could be used to get look from Picture 3:

Picture 2


Picture 3


To achieve this, put background image to img (or any other) sub-folder in your project. In all #ulNav sections, replace background: #224D6F; with background: url(../images/menu-bg.gif) top left repeat-x;.

XSL - Create Bar Chart

When using XSL templates to transform XML data to HTML, there is a frequent need to present some sort of statistics, in a form different than simple table. Chart could be a common choice. Bar chart could be generated from input data using simple XSL/HTML tags.

Following example uses four ranges on X axis, with respective percentages presented as bars for each range. Y axis is divided into five ranges.

<table cellSpacing="0" cellPadding="0" align="center" style="border-right: white 0px solid; border-top: white 0px solid; ; border-left: white 0px solid; border-bottom: white 0px solid; text-align: center">
 <tbody>
<tr>
   <td style="border-right: white 0px solid; border-top: black 1px solid; border-left: black 1px solid; width: 30px; border-bottom: white 0px solid"/>
   <td style="border-right: white 0px solid; border-top: black 1px solid; border-left: white 0px solid; width: 20px; border-bottom: white 0px solid"/>
   <td style="border-right: white 0px solid; border-top: black 1px solid; border-left: white 0px solid; width: 60px; border-bottom: white 0px solid"/>
   <td style="border-right: white 0px solid; border-top: black 1px solid; border-left: white 0px solid; width: 60px; border-bottom: white 0px solid"/>
   <td style="border-right: white 0px solid; border-top: black 1px solid; border-left: white 0px solid; width: 60px; border-bottom: white 0px solid"/>
   <td style="border-right: white 0px solid; border-top: black 1px solid; border-left: white 0px solid; width: 60px; border-bottom: white 0px solid"/>
   <td style="border-right: black 1px solid; border-top: black 1px solid; border-left: white 0px solid; width: 10px; border-bottom: white 0px solid; height: 10px"/>
  </tr>
<tr>
   <td style="border-right: white 0px solid; border-top: white 0px solid; border-left: black 1px solid; border-bottom: white 0px solid"/>
   <td rowSpan="2" style="border-right: white 0px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid"/>
   <td rowSpan="10" vAlign="bottom" align="center"
       style="border-right: white 0px solid; padding-right: 0px; border-top: black 1px solid; padding-left: 0px; font-size: 1px; padding-bottom: 0px; border-left: black 1px solid; padding-top: 0px; border-bottom: black 1px solid">
    <table style="border-right: black 1px solid; border-top: black 1px solid; ; border-left: black 1px solid; width: 80%; border-bottom: white 0px solid">
     <tbody>
<tr style="background-color: lime; height: 15px;">
       <td style="border-right: white 0px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid"/>
      </tr>
</tbody>
    </table>
</td>
   <td rowSpan="10" vAlign="bottom" align="center"
       style="border-right: white 0px solid; padding-right: 0px; border-top: black 1px solid; padding-left: 0px; font-size: 1px; padding-bottom: 0px; border-left: white 0px solid; padding-top: 0px; border-bottom: black 1px solid">
    <table style="border-right: black 1px solid; border-top: black 1px solid; ; border-left: black 1px solid; width: 80%; border-bottom: white 0px solid">
     <tbody>
<tr style="background-color: yellow; height: 35px;">
       <td style="border-right: white 0px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid"/>
      </tr>
</tbody>
    </table>
</td>
   <td rowSpan="10" vAlign="bottom" align="center"
       style="border-right: white 0px solid; padding-right: 0px; border-top: black 1px solid; padding-left: 0px; font-size: 1px; padding-bottom: 0px; border-left: white 0px solid; padding-top: 0px; border-bottom: black 1px solid">
    <table style="border-right: black 1px solid; border-top: black 1px solid; ; border-left: black 1px solid; width: 80%; border-bottom: white 0px solid">
     <tbody>
<tr style="background-color: cyan; height: 20px;">
       <td style="border-right: white 0px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid"/>
      </tr>
</tbody>
    </table>
</td>
   <td rowSpan="10" vAlign="bottom" align="center"
       style="border-right: black 1px solid; padding-right: 0px; border-top: black 1px solid; padding-left: 0px; font-size: 1px; padding-bottom: 0px; border-left: white 0px solid; padding-top: 0px; border-bottom: black 1px solid">
    <table style="border-right: black 1px solid; border-top: black 1px solid; ; border-left: black 1px solid; width: 80%; border-bottom: white 0px solid">
     <tbody>
<tr style="background-color: magenta; height: 30px;">
       <td style="border-right: white 0px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid"/>
      </tr>
</tbody>
    </table>
</td>
   <td style="border-right: black 1px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid; height: 10px"/>
  </tr>
<tr>
   <td rowSpan="2" style="border-right: white 0px solid; border-top: white 0px solid; border-left: black 1px solid; border-bottom: white 0px solid">80%</td>
   <td style="border-right: black 1px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid; height: 10px"/>
  </tr>
<tr>
   <td rowSpan="2" style="border-right: white 0px solid; border-top: black 1px solid; border-left: white 0px solid; border-bottom: white 0px solid"/>
   <td style="border-right: black 1px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid; height: 10px"/>
  </tr>
<tr>
   <td rowSpan="2" style="border-right: white 0px solid; border-top: white 0px solid; border-left: black 1px solid; border-bottom: white 0px solid">60%</td>
   <td style="border-right: black 1px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid; height: 10px"/>
  </tr>
<tr>
   <td rowSpan="2" style="border-right: white 0px solid; border-top: black 1px solid; border-left: white 0px solid; border-bottom: white 0px solid"/>
   <td style="border-right: black 1px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid; height: 10px"/>
  </tr>
<tr>
   <td rowSpan="2" style="border-right: white 0px solid; border-top: white 0px solid; border-left: black 1px solid; border-bottom: white 0px solid">40%</td>
   <td style="border-right: black 1px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid; height: 10px"/>
  </tr>
<tr>
   <td rowSpan="2" style="border-right: white 0px solid; border-top: black 1px solid; border-left: white 0px solid; border-bottom: white 0px solid"/>
   <td style="border-right: black 1px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid; height: 10px"/>
  </tr>
<tr>
   <td rowSpan="2" style="border-right: white 0px solid; border-top: white 0px solid; border-left: black 1px solid; border-bottom: white 0px solid">20%</td>
   <td style="border-right: black 1px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid; height: 10px"/>
  </tr>
<tr>
   <td rowSpan="2" style="border-right: white 0px solid; border-top: black 1px solid; border-left: white 0px solid; border-bottom: white 0px solid"/>
   <td style="border-right: black 1px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid; height: 10px"/>
  </tr>
<tr>
   <td style="border-right: white 0px solid; border-top: white 0px solid; border-left: black 1px solid; border-bottom: white 0px solid"/>
   <td style="border-right: black 1px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid; height: 10px"/>
  </tr>
<tr>
   <td style="border-right: white 0px solid; border-top: white 0px solid; border-left: black 1px solid; border-bottom: white 0px solid"/>
   <td style="border-right: white 0px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid"/>
   <td style="border-right: white 0px solid; border-top: white 0px solid; font-weight: bold; font-size: 10pt; border-left: white 0px solid; border-bottom: white 0px solid">Range 1</td>
   <td style="border-right: white 0px solid; border-top: white 0px solid; font-weight: bold; font-size: 10pt; border-left: white 0px solid; border-bottom: white 0px solid">Range 2</td>
   <td style="border-right: white 0px solid; border-top: white 0px solid; font-weight: bold; font-size: 10pt; border-left: white 0px solid; border-bottom: white 0px solid">Range 3</td>
   <td style="border-right: white 0px solid; border-top: white 0px solid; font-weight: bold; font-size: 10pt; border-left: white 0px solid; border-bottom: white 0px solid">Range 4</td>
   <td style="border-right: black 1px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: white 0px solid; height: 10px"/>
  </tr>
<tr>
   <td style="border-right: white 0px solid; border-top: white 0px solid; border-left: black 1px solid; border-bottom: black 1px solid"/>
   <td style="border-right: white 0px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: black 1px solid"/>
   <td style="border-right: white 0px solid; border-top: white 0px solid; font-size: 10pt; border-left: white 0px solid; border-bottom: black 1px solid">15%</td>
   <td style="border-right: white 0px solid; border-top: white 0px solid; font-size: 10pt; border-left: white 0px solid; border-bottom: black 1px solid">35%</td>
   <td style="border-right: white 0px solid; border-top: white 0px solid; font-size: 10pt; border-left: white 0px solid; border-bottom: black 1px solid">20%</td>
   <td style="border-right: white 0px solid; border-top: white 0px solid; font-size: 10pt; border-left: white 0px solid; border-bottom: black 1px solid">30%</td>
   <td style="border-right: black 1px solid; border-top: white 0px solid; border-left: white 0px solid; border-bottom: black 1px solid; height: 10px"/>
  </tr>
</tbody>
</table>


The basic point is to create regular table. For example with 4 ranges on X scale and 5 ranges on Y scale, table should have 13 rows, with 7 columns in each row. Some columns are spanned (merged) over multiple rows, allowing labels and bars to be defined. The outlook of "raw" table, with hidden borders shown dotted, is presented in Picture 1:
Picture 1
When merger is implemented to create row for bars, they are simply defined using heights in pixels.

Replace hardwired values from example with values read from source XML file.

The resulting HTML in browser is shown in Picture 2:

Picture 2