Thứ Hai, 20 tháng 4, 2015

Search unstructured strings by Binary Search or Hash Table


This page will introduce a technique  using to search unstructured strings by using Binary Search, or Hash Table. It can be use to search  books, news, web pages, music lyrics and others.

 Advantages:
1.       Reducing searching scope.
2.       Applying searching algorithms such as: Binary Search, Hash Table.

Disadvantages:
1.       data must be prepared before searching
2.       Need space for new database.

Example:

The problem: 

Giving a text T=  “a d b e a f c b e a d e a f” and a pattern P = “e a f”,

Question:

Does P is a substring of T ?
If yes, how many times does P appear in T ? and where is P in T
( in this example, it only uses Binary Search algorithm )
The idea:
1.        Number all words in text T.
2.       Group similar words of T in one array. An array contains index number of each word.
3.       Convert  array words to integers and sort them from smallest to the largest
4.       Convert all words of pattern P to integer
5.       Find arrays of T that similar to words of P (apply binary search algorithm)
6.       Compare index numbers of those arrays (apply binary search algorithm), we can find that P is a substring of T or not.  position of P in T
(  this example only use binary search algorithm  )
Solving the problem:

Step 1: Index all words in text T

a
d
b
e
a
f
c
b
e
a
d
e
a
f
0
1
2
3
4
5
6
7
8
9
10
11
12
13
  
Step 2: Group similar words in one array, an array contains index number of those words

Array
Array contain
Length of array
a
0,4,9,12
4
b
2,7
2
c
6
1
d
1,10
2
e
3,8,11
3
f
5,13
2
   
Step 3: convert words to integers and sort them form smallest to largest.

Array
Array contain
Length of array
97 (a)
0,4,9,12
4
98 (b)
2,7
2
99 (c)
6
1
100 (d)
1,10
2
101 (e)
3,8,11
3
102 (f)
5,13
2

finishing preparation of text T, the next step prepares pattern P and search

Step 4: convert pattern P to integers.

Word
integer
e
101
a
97
f
102

Step 5: select arrays “101 (e)”, “97 (a)”, and “102 (f)” (apply binary search algorithm)and compare these lengths. Selecting those arrays because their words are similar to pattern P’s words.

Array
Array contain
Length of array
97 (a)
0,4,9,12
4
101 (e)
3,8,11
3
102 (f)
5,13
2

Because array “102 (f)” length is 2 which is the smallest length. So we start from “f”. It means that f index number is 0, from that we calculate “e” and “a” index number.

 P = “e a f”
e
a
f
-2
-1
0

Step 6: searching

selecting each number form array “102 (f)” and calculate index numbers of word “e” and “a”. If array “97 (a)” and “101 (e)” contain those numbers, we can conclude that pattern p is a substring of text T. If not, P is not substring of T.
1.       F = 5
e
a
f
3
4
5
(apply binary search algorithm) we find that array “101 (e)” contains 3 and array “97 (a)” contains 4. So P is a substring  of T at 3-5.

2.       F = 13
e
a
f
11
12
13

 (apply binary search algorithm) we find that array “101 (e)” contains 11 and array “97 (a)” contains 12. So P is a substring  of T at 11-13.

Finish :D.  
We also can apply Hash table or others.

Some words

form "Step 5", we reduce searching scope, Lest take an example, if we have a book, which has 1 million words, after we index and array them, we may have 10000 arrays and average, each array has 100 words. We search a sentence, which has 10 words and those words do not repeat. so our scope is 10 *100 = 1000 words. Comparing with 1 million words, new scope is smaller 1000 times than old one.

Step 6: If we use Binary search, not hash table, we also can reduce searching scope.

Example: we have pattern is P="a b",  2 arrays A and B, which are increasing arrays form text T. 

Array A start number is 9 and end number is 20 .A[9...20].
Array B start number is 1 and end number is 15. B[1...15]

If we find that the middle number in array B is 8, [1 ... 8][8 ... 15], because 8 < 9,which is the start number of array A. So we can ignore array [1 .. 8].

If we find that the middle number in array A is 16, [9 ... 16][16 ... 20], because 16 > 15,which is the end number of array B. So we can ignore array [16 ... 20].

Conclusion:  

Decreasing searching scope and apply search algorithms can improve searching performance.

thank.

Thứ Tư, 1 tháng 10, 2014

Application: Pro Auto Redial | Repeat call

Pro Auto Redial - Repeat call

Introduction:
+This app redials a phone number many times.
+Making the phone auto hang up with setting time.
Application's purpose
+Many telecom companies offer free calling for the first 10,20,.. minutes. "Pro Auto Redial" helps you control calling time and saving phone money.
+You can show your lover that you love them so much by making many miss call, when they don't accept your call ^^.
Main Features:
+Auto redial
+Auto hang up
+Fast redial
How to use this application:
1. Enter phone number or press on person icon to chose a phone number in contact
2. Press on first text to change between minute and second
3. Drag first bar to set redial duration
4. Press on second text to change between minute and second
5. Drag second bar to set hang up duration
6. Press on "Call" button to start
7. Press on "End call" Button to stop loop
Important
+"Pro Auto Redial" may not work on some Android version. So you should make a small test after download.
1. Chose a phone number.
2. Set hang up duration equal 10-15 seconds
3. Press "Call" button and waiting 10-15 seconds to check end call or not.
Support language.
+English
+Tiếng Việt
Note
+If you like "Pro Auto Redial", you can support us by rating it, sharing it, and downloading other apps
+If you have any questions or new idea to improve "Pro Auto Redial", please sending to
email: trunglehuynh@gmail.com

Link: play.google.com

Thứ Ba, 30 tháng 9, 2014

Application: Smart Alarm Clock

Smart Alarm Clock

Introduction:
"Smart Alarm Clock” is a smart application help you never be late and show your style. Have you ever been late? Because you did not set alarm or you set alarm but you turned off your alarm only to fall back to sleep. Do you want to use a simple interface application and this can be designed by yourself. If the answer is YES, Smart Alarm Clock is built for you.
Main Functions:
-100% Free
-Simple interface (Interface can be designed by yourself, showing your personal style)
-Repeat each day in week.
-Auto dismiss within limit time.
-3 Dismiss methods:
-----Press on screen button
-----Enter numbers ( avoid turn off alarm when you do not complete wake up )
-----solve math problems ( avoid turn off alarm when you do not complete wake up )
-Alarm by Ringtones
- Alarm by Songs
-Change Volume
Support language:
+English
+Tiếng Việt
Email: trunglehuynh@gmail.com