0
$\begingroup$

Why does an NFA that accepts/rejects bit strings implemented with a Recursive Backtracking algorithm outperform one that is written using a Parallel Bitmap search?

set up two tests for these algorithms, to evaluate on both different length strings, and different numbers of inputs:

  • First, I created sets of 1,000 random bit strings of length n, where my sets were n = [4, 8, 16, 32, 64].

  • Second, I tested these on input.txt files with varying amounts of strings. In all cases, bit strings were length 10 with files of varying amounts of strings( 10^n strings with n = [1:6]).

  • I timed each of these tests using the Python .time module.

I expected Parallel Bitmap Search to run faster, but the Recursive method was more efficient.

Below is the code for the bit-mapped parallel search method:

"""
 The current set of states, encoded bitwise: 
 state i is represented by the bit 1<<i.
"""
stateSet = 0

"""
 Reset the current state set to {the start state}.
"""
def reset():
    global stateSet
    stateSet = 1<<0


"""
 The transition function represented as an array.
 The set of next states from a given state s and 
 character c is at delta[s,c-'0'].
"""
#rows = states
#cols = transitions
delta =  [[1<<0|1<<1, 1<<0],\ 
          [1<<2,0],\ 
          [1<<2,1<<2]]



"""
 Make one transition from state-set to state-set on 
 each char in the given string.
 @param inp the String to use
"""
def process(inp):
    global stateSet
    for i in range(len(inp)):
        c = inp[i]
        nextSS = 0  # next state set, initially empty
        for s in range(3):  # for each state s
            if (stateSet&(1<<s)) != 0:  # if maybe in s
                try:
                    nextSS |= delta[s][int(c)]
                except:
                    # in effect, nextSS |= 0
                    pass
        stateSet = nextSS # new state set after c

Recursive Method:

    class State():
        def __init__(self,name,is_start_state,is_final_state):
            """
            *** constructor ***
            1. name             , the name of the state, i.e. q0
            2. is_start_state   , the name of the state, i.e. True if is start state
            3. is_final_state   , the name of the state, i.e. False if not final state
            4. transitions      , the transition table, contents are filled by add_transitions()
            """
            self.name = name
            self.is_start_state = is_start_state
            self.is_final_state = is_final_state
            self.transitions = {}                   #empty dict for transition table


        def add_transitions(self,string, target_states):

            #trans = (string, target_states)
            self.transitions[string] = target_states


   # NFA below

    q0 = State("q0",True,False)
    q1 = State("q1",False,False)
    q2 = State("q2", False, True)
    #q0 start, not final
    q0.add_transitions("0",[q0,q1])    #adds an entry to the transitions dict:{ "0":[q0]}
    q0.add_transitions("1",[q0]) 
    #q1 not start, not final
    q1.add_transitions("0",[q2])
    #q2 not start, final
    q2.add_transitions("0",[q2])
    q2.add_transitions("1",[q2])


    states = [q0,q1,q2]


        """
         Test whether there is some path for the NFA to
         reach an accepting state from the given state,
         reading the given string at the given character
         position.
         @param state the current state
         @param inp the input string
         @param pos index of the next char in the string
         @return true if the NFA accepts on some path
        """


        def accept_step(state, inp, pos): 
            if pos == len(inp): # if no more to read
                return state.is_final_state   # accept if the reached state is final state

            c = inp[pos]    # get char

            try:
                nextStates = state.transitions[c] #char is dict key for transitions
            except:
                return False    # no transition, just reject


            for nextState in nextStates:
                if accept_step(nextState, inp, (pos+1)):
                    return True
            return False    # all moves fail, return false


        """ 
         Test whether the NFA accepts the string.
         @param in the String to test
         @return true if the NFA accepts on some path
        """
        def accepts(str_input):
            return accept_step(states[0], str_input, 0) # start in q0 at char 0
$\endgroup$
  • $\begingroup$ What is a 'Parallel Bitmap search' and how does it facilitate NFA acceptance/rejection? Why do you claim that one method outperforms the other? Some benchmark or experiment? If so, please link to or describe it. Additionally, what did you try to answer this question? Where did you get stuck? Did you expect that the bitmap search would outperform the recursive backtracking algorithm? If so, why? $\endgroup$ – Discrete lizard Jan 21 '18 at 15:17
  • $\begingroup$ In experiment, the backtracking was faster. In the recursive method, I created the states as objects and assigned the possible TO states based on inputs one by one, then recursively ran through each character in string and would back up and re try if it did not reach accepting state. In parallel search, I made an array with the sets of possible states based on bit operations i.e {1<<0 , 0 << 0 | 0 << 1} on first row represents from q0 0 goes to q1 and 1 goes to q0 OR q1. I expected the parallel method to run faster than backtracking since it would not waste time on failed runs $\endgroup$ – foobarbaz Jan 21 '18 at 15:44
  • $\begingroup$ Could you edit your question to add the information from your comment? In particular, it would help to describe your experiment and the algorithm of the different methods in detail. Often, differences in actual running times of programs depend crucially on their implementation, unless one underlying algorithm is much faster than the other. However, it may also be a result of the a conceptual difference between the algorithms. To determine whether this is the case, I think more detail on the algorithms is needed. $\endgroup$ – Discrete lizard Jan 21 '18 at 15:53
  • $\begingroup$ @Discretelizard I updated my original question with more context. I am new to finite automaton and CS in general so I was not sure how much context was needed to answer questions like these. $\endgroup$ – foobarbaz Jan 21 '18 at 18:14
  • 1
    $\begingroup$ Good! Although it would help even more if you could give a high level description of your code instead of the actual code, especially for the bit-mapped parallel search method (I think more people may be familiar with the recursive backtracking method). See this answer for an example of a 'high-level' description of an algorithm (you might want to use more words than that example, but there's no need for code). $\endgroup$ – Discrete lizard Jan 21 '18 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.