####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### ####################################################### |
Algorithm: Discrete Probability Detector Input: |
'################################################################################################### '# John Wiley & Sons, Inc. # '# # '# Book: Markov Chains: From Theory To Implementation And Experimentation # '# Author: Dr. Paul Gagniuc # '# Data: 01/05/2017 # '# # '# Title: # '# Discrete Probability Detector # '# # '# Short Description: # '# The purpose of this algorithm is to convert any string into a probability matrix. # '#_______________________ # '# Detailed description: \ # '# This algorithm is an advanced variation of the "ExtractProb" function from the book. The # '# main difference between "ExtractProb" function and the DPD algorithm is the automatic # '# identification of states. # '#_________________________________________________________________________________________________# '# Initially, the states are identified in the first phase. Each new letter found in "S" is # '# appended to the string forming in variable "a". Thus, variable "a" gradually increases until # '# all types of letters from "S" are identified. # '#_________________________________________________________________________________________________# '# In the second phase the elements of matrix "m" are filled with zero values for later # '# purposes. Also, in the second phase the first column of matrix "e" is filled with letters # '# found in variable "a", and the second column of matrix "e" is filled with zero values for # '# later use. # '#_________________________________________________________________________________________________# '# In the third phase, the transitions between letters of "S" are counted and stored in # '# matrix "m". # '# The strategy in this particular case is to fill matrix "m" with transition counts before the # '# last letter in "S" is reached. In this case, the first column of matrix "e" already contains # '# the letters from variable "a". The two components of vector "l" contain the "i" and "i+1" # '# letters from "S". The count of individual transitions between letters is made by a comparison # '# between vector "l" and the elements from the first column of matrix "e". The number of rows # '# in matrix "m" and matrix "e" is the same, namely "d". Therefore, an extra loop can be avoided # '# by mapping matrix "m" through a coordinate system. For instance, if the letter from position # '# "i" in "S" stored in "l[0]" and the letter from "j" row in matrix "e" (e[j][0]) are the same # '# then variable "r = j". Likewise, if the letter "i+1" stored in l[1] and the letter from e[j][0] # '# are the same then variable "c = j". Variable "r" represents the rows of matrix "m", whereas # '# variable "c" represents the columns of matrix "m" (m[r][c]). # '# Thus, at each step through "S", an element of matrix "m" is always incremented according to # '# the coordinates received from "r" and "c". This "coordinate" approach greatly increases the # '# processing speed of the algorithm. The number of loops = (k-1)*d, where "d" represents the # '# number of states (or letter types), and "k" is the number of letters in "S". When the letter # '# stored in "l[0]" and the letter from "j" row in matrix "e" are the same, the second column of # '# matrix "e" is also incremented. The second column of matrix "e" stores the number of # '# appearances for each type of letter in "S". # '#_________________________________________________________________________________________________# '# In the fourth phase, the counts from matrix "m" elements are divided by the counts from the # '# second column of matrix "e". The result of this division is stored in the same position in # '# matrix "m", and represents a transition probability. # '#_________________________________________________________________________________________________# '# # '# Special considerations: # '# # '# If a state at the end of "S" (ie HAHAAAHQ) does not occur in the rest of "S" then matrix "m" # '# will contain a row with all elements on zero. Since it is at the end of "S", the letter does # '# not make a transition to anything. If a state from the beginning of "S" (ie. QHAHAAAH) does # '# not occur in the rest of "S" then matrix "m" will contain a column with all elements on zero. # '# Since the first letter it is only seen at the beginning of "S", no other letter makes a # '# transition to it. # '# # '# The meaning of variables: # '# _____________________________________________________________________________________ # '# S = |The string that is being analyzed. _| # '# _____________________________________________________________________________________ # '# q = |It is a flag variable with initial value of 1. The value of q becomes zero only if a | # '# |letter x in the "S" string coresponds with a letter y in the "a" string. _| # '# _____________________________________________________________________________________ # '# a = |The variable that holds the letters representing the states. The variable gradually | # '# |increases in length as the "S" string is analyzed. At each loop, a new letter is | # '# |added to variable "a" only if the value of q becomes zero. Thus, at the end of the | # '# |first loop the number of letters in the variable is equal to the total number | # '# |of states. _| # '# _____________________________________________________________________________________ # '# d = |Represents the total number of states and is the length of "a" variable. _| # '# _____________________________________________________________________________________ # '# m = |The main probability matrix which the function produces. _| # '# _____________________________________________________________________________________ # '# k = |Represents the length of the "S" string. _| # '# _____________________________________________________________________________________ # '# e = |It is a matrix with two columns, namely column 0 and 1. Column 0 stores all the | # '# |letters found in "a". Column 1 stores the number of appearances for each type | # '# |of letter in "S". _| # '# _____________________________________________________________________________________ # '# l = |Is a vector with two components. Vector "l" contains the "i" and "i+1" letters | # '# |from "S". _| # '# # '################################################################################################### var s = "HAHAAAHA"; |--------------[ Phase one ]--------------| var x; var y; var a = ""; var k = s.length; for(var i=0; i<=k; i++){ var q = 1; for(var j=0; j<=a.length; j++){ x = s.substr(i, 1); y = a.substr(j, 1); if (x === y) {q = 0;} } if (q === 1) {a = a + x;} } |--------------[ Phase two ]--------------| var d = a.length; var m = []; var e = []; var l = []; for(var i=1; i<=d; i++){ m[i]=[]; e[i]=[]; for(var j=1; j<=d; j++){ m[i][j]=0; if (j === 1) { e[i][0]=a.substr(i-1, 1); e[i][1]=0; } } } |-------------[ Phase three ]-------------| l[0]=""; l[1]=""; for(var i=0; i<s.length-1; i++){ l[0] = s.substr(i, 1); l[1] = s.substr(i + 1, 1); for(var j=1; j<=d; j++){ if (l[0] === e[j][0]) { e[j][1] = e[j][1] + 1; r = j; } if (l[1] === e[j][0]) {c=j;} } m[r][c] = m[r][c] + 1; } |-------------[ Phase four ]--------------| for(var i=1; i<=d; i++){ for(var j=1; j<=d; j++){ if (e[i][1] > 0) { m[i][j]=m[i][j]/e[i][1]; } } } |----------------[ END ]------------------|