class Filter(object):
    """Filter base class.
    """
    def __init__(self, allow_missing=False):
        self.allow_missing = allow_missing

    def filter_candset(self, candset,
                       candset_l_key_attr, candset_r_key_attr,
                       ltable, rtable,
                       l_key_attr, r_key_attr,
                       l_filter_attr, r_filter_attr,
                       n_jobs=1, show_progress=True):
        """Finds candidate matching pairs of strings from the input candidate 
        set.

        Args:
            candset (DataFrame): input candidate set.

            candset_l_key_attr (string): attribute in candidate set which is a 
                key in left table.

            candset_r_key_attr (string): attribute in candidate set which is a 
                key in right table.

            ltable (DataFrame): left input table.

            rtable (DataFrame): right input table.

            l_key_attr (string): key attribute in left table.

            r_key_attr (string): key attribute in right table.

            l_filter_attr (string): attribute in left table on which the filter 
                should be applied.                                              
                                                                                
            r_filter_attr (string): attribute in right table on which the filter
                should be applied.

            n_jobs (int): number of parallel jobs to use for the computation    
                (defaults to 1). If -1 is given, all CPUs are used. If 1 is     
                given, no parallel computing code is used at all, which is      
                useful for debugging. For n_jobs below -1,                      
                (n_cpus + 1 + n_jobs) are used (where n_cpus is the total       
                number of CPUs in the machine). Thus for n_jobs = -2, all CPUs  
                but one are used. If (n_cpus + 1 + n_jobs) becomes less than 1, 
                then no parallel computing code will be used (i.e., equivalent  
                to the default).
                                                                                
            show_progress (boolean): flag to indicate whether task progress     
                should be displayed to the user (defaults to True). 

        Returns:
            An output table containing tuple pairs from the candidate set that 
            survive the filter (DataFrame).
        """

        # check if the input candset is a dataframe
        validate_input_table(candset, 'candset')

        # check if the candset key attributes exist
        validate_attr(candset_l_key_attr, candset.columns,
                      'left key attribute', 'candset')
        validate_attr(candset_r_key_attr, candset.columns,
                      'right key attribute', 'candset')

        # check if the input tables are dataframes
        validate_input_table(ltable, 'left table')
        validate_input_table(rtable, 'right table')

        # check if the key attributes filter join attributes exist
        validate_attr(l_key_attr, ltable.columns,
                      'key attribute', 'left table')
        validate_attr(r_key_attr, rtable.columns,
                      'key attribute', 'right table')
        validate_attr(l_filter_attr, ltable.columns,
                      'filter attribute', 'left table')
        validate_attr(r_filter_attr, rtable.columns,
                      'filter attribute', 'right table')

        # check if the filter attributes are not of numeric type                      
        validate_attr_type(l_filter_attr, ltable[l_filter_attr].dtype,          
                           'filter attribute', 'left table')                    
        validate_attr_type(r_filter_attr, rtable[r_filter_attr].dtype,          
                           'filter attribute', 'right table')

        # check if the key attributes are unique and do not contain 
        # missing values
        validate_key_attr(l_key_attr, ltable, 'left table')
        validate_key_attr(r_key_attr, rtable, 'right table')

        # check for empty candset
        if candset.empty:
            return candset

        # Do a projection on the input dataframes to keep only required 
        # attributes. Note that this does not create a copy of the dataframes. 
        # It only creates a view on original dataframes.
        ltable_projected = ltable[[l_key_attr, l_filter_attr]]
        rtable_projected = rtable[[r_key_attr, r_filter_attr]]

        # computes the actual number of jobs to launch.
        n_jobs = min(get_num_processes_to_launch(n_jobs), len(candset))
        
        if n_jobs <= 1:
            # if n_jobs is 1, do not use any parallel code.                     
            output_table =  _filter_candset_split(candset,
                                         candset_l_key_attr, candset_r_key_attr,
                                         ltable_projected, rtable_projected,
                                         l_key_attr, r_key_attr,
                                         l_filter_attr, r_filter_attr,
                                         self, show_progress)
        else:
            # if n_jobs is above 1, split the candset into n_jobs splits and    
            # filter each candset split in a separate process.
            candset_splits = split_table(candset, n_jobs)
            results = Parallel(n_jobs=n_jobs)(delayed(_filter_candset_split)(
                                      candset_splits[job_index],
                                      candset_l_key_attr, candset_r_key_attr,
                                      ltable_projected, rtable_projected,
                                      l_key_attr, r_key_attr,
                                      l_filter_attr, r_filter_attr,
                                      self,
                                      (show_progress and (job_index==n_jobs-1)))
                                          for job_index in range(n_jobs))
            output_table = pd.concat(results)

        return output_table         def get_overlap_threshold(l_num_tokens, r_num_tokens,
                          sim_measure_type, threshold, tokenizer):
    """Computes the minimum overlap needed between the tokens to satisfy the          
    threshold. 
    """

    if sim_measure_type == 'COSINE':
        return ceil(round(threshold * sqrt(l_num_tokens * r_num_tokens), 4))
    elif sim_measure_type == 'DICE':
        return ceil(round((threshold / 2) * (l_num_tokens + r_num_tokens), 4))
    elif sim_measure_type == 'EDIT_DISTANCE':
        return max(l_num_tokens + tokenizer.qval - 1,
                   r_num_tokens + tokenizer.qval - 1) - tokenizer.qval + 1 - \
               tokenizer.qval * threshold
    elif sim_measure_type == 'JACCARD':
        return ceil(round((threshold / (1 + threshold)) * 
                          (l_num_tokens + r_num_tokens), 4))
    elif sim_measure_type == 'OVERLAP':
        return threshold def get_prefix_length(num_tokens, sim_measure_type, threshold, tokenizer):
    """Computes prefix length.                                     

    References:                                                                 
        * String Similarity Joins: An Experimental Evaluation, VLDB 2014.       
    """

    if num_tokens == 0:
        return 0

    if sim_measure_type == 'COSINE':
        return int(num_tokens -
                   ceil(threshold * threshold * num_tokens) + 1)
    elif sim_measure_type == 'DICE':
        return int(num_tokens -
                   ceil((threshold / (2 - threshold)) * num_tokens) + 1)
    elif sim_measure_type == 'EDIT_DISTANCE':
        return min(tokenizer.qval * threshold + 1, num_tokens)
    elif sim_measure_type == 'JACCARD':
        return int(num_tokens - ceil(threshold * num_tokens) + 1)
    elif sim_measure_type == 'OVERLAP':
        return max(num_tokens - threshold + 1, 0) def get_size_lower_bound(num_tokens, sim_measure_type, threshold):
    """Computes lower bound for size filter.

    Specifically, computes lower bound on the number of tokens a string must 
    have in order to obtain a similarity score that satisfies the input 
    threshold with a string containing number of tokens, specified by 
    'num_tokens'.
    
    References:
        * String Similarity Joins: An Experimental Evaluation, VLDB 2014.
    """

    if sim_measure_type == 'COSINE':
        return int(ceil(round(threshold * threshold * num_tokens, 4)))
    elif sim_measure_type == 'DICE':
        return int(ceil(round((threshold / (2 - threshold)) * num_tokens, 4)))
    elif sim_measure_type == 'EDIT_DISTANCE':
        return num_tokens - threshold
    elif sim_measure_type == 'JACCARD':
        return int(ceil(round(threshold * num_tokens, 4)))
    elif sim_measure_type == 'OVERLAP':
        return threshold def get_size_upper_bound(num_tokens, sim_measure_type, threshold):
    """Computes upper bound for size filter.                                     
                                                                                
    Specifically, computes upper bound on the number of tokens a string must     
    have in order to obtain a similarity score that satisfies the input 
    threshold with a string containing number of tokens, specified by 
    'num_tokens'.            
                                                                                
    References:                                                                 
        * String Similarity Joins: An Experimental Evaluation, VLDB 2014.       
    """

    if sim_measure_type == 'COSINE':
        return int(floor(round(num_tokens / (threshold * threshold), 4)))
    elif sim_measure_type == 'DICE':
        return int(floor(round(
            ((2 - threshold) / threshold) * num_tokens, 4)))
    elif sim_measure_type == 'EDIT_DISTANCE':
        return num_tokens + threshold
    elif sim_measure_type == 'JACCARD':
        return int(floor(round(num_tokens / threshold, 4)))
    elif sim_measure_type == 'OVERLAP':
        return maxsize class PositionIndex(Index):
    """Builds a position index on the input column in the input table.                                                                  
                                                                                
    Position index is used by position filter, dice join, cosine join and 
    jaccard join.               
    """   

    def __init__(self, table, index_attr, tokenizer, 
                 sim_measure_type, threshold, token_ordering):
        self.table = table
        self.index_attr = index_attr
        self.tokenizer = tokenizer
        self.sim_measure_type = sim_measure_type
        self.threshold = threshold
        self.token_ordering = token_ordering
        self.index = None
        self.size_cache = None
        self.min_length = maxsize
        self.max_length = 0
        super(self.__class__, self).__init__()

    def build(self, cache_empty_records=True, cache_tokens=False):
        """Build position index."""
        self.index = {}
        self.size_cache = []
        cached_tokens = []
        empty_records = []
        row_id = 0
        for row in self.table:
            # tokenize string and order the tokens using the token ordering     
            index_string = row[self.index_attr]
            index_attr_tokens = order_using_token_ordering(
                self.tokenizer.tokenize(index_string), self.token_ordering)

            # compute prefix length
            num_tokens = len(index_attr_tokens)
            prefix_length = get_prefix_length(
                                num_tokens,
                                self.sim_measure_type, self.threshold,
                                self.tokenizer)

            # update the index
            pos = 0
            for token in index_attr_tokens[0:prefix_length]:
                if self.index.get(token) is None:
                    self.index[token] = []
                self.index.get(token).append((row_id, pos))
                pos += 1

            self.size_cache.append(num_tokens)

            # keep track of the max size and min size.
            if num_tokens < self.min_length:
                self.min_length = num_tokens

            if num_tokens > self.max_length:
                self.max_length = num_tokens

            # if cache_tokens flag is set to True, the store the tokens. 
            if cache_tokens:
                cached_tokens.append(index_attr_tokens)

            if cache_empty_records and num_tokens == 0:
                empty_records.append(row_id)

            row_id += 1            

        return {'cached_tokens' : cached_tokens,
                'empty_records' : empty_records}

    def probe(self, token):
        """Probe position index using the input token."""
        return self.index.get(token, [])

    def get_size(self, row_id):
        return self.size_cache[row_id] def convert_dataframe_to_array(dataframe, proj_attrs, join_attr, 
                               remove_nan=True):
    if remove_nan:
        projected_dataframe = dataframe[proj_attrs].dropna(0, 
                                                           subset=[join_attr])
    else:
        projected_dataframe = dataframe[proj_attrs]

    return projected_dataframe.values def find_output_attribute_indices(original_columns, output_attributes):
    output_attribute_indices = []
    if output_attributes is not None:
        for attr in output_attributes:
            output_attribute_indices.append(original_columns.index(attr))
    return output_attribute_indices def get_attrs_to_project(out_attrs, key_attr, join_attr):
    # this method assumes key_attr has already been removed from
    # out_attrs, if present.
    proj_attrs = [key_attr, join_attr]

    if out_attrs is not None:
        for attr in out_attrs:
            if attr != join_attr:
                proj_attrs.append(attr)

    return proj_attrs def get_num_processes_to_launch(n_jobs):        
    # determine number of processes to launch parallely
    num_procs = n_jobs
    if n_jobs < 0:
        num_cpus = multiprocessing.cpu_count()
        num_procs = num_cpus + 1 + n_jobs
    return max(num_procs, 1) def get_output_header_from_tables(l_key_attr, r_key_attr,
                                  l_out_attrs, r_out_attrs,
                                  l_out_prefix, r_out_prefix):
    output_header = []

    output_header.append(l_out_prefix + l_key_attr)

    output_header.append(r_out_prefix + r_key_attr)

    if l_out_attrs:
        for l_attr in l_out_attrs:
            output_header.append(l_out_prefix + l_attr)

    if r_out_attrs:
        for r_attr in r_out_attrs:
            output_header.append(r_out_prefix + r_attr)

    return output_header def get_output_row_from_tables(l_row, r_row,
                               l_key_attr_index, r_key_attr_index, 
                               l_out_attrs_indices=None,
                               r_out_attrs_indices=None):
    output_row = []
    
    # add ltable id attr
    output_row.append(l_row[l_key_attr_index])

    # add rtable id attr
    output_row.append(r_row[r_key_attr_index])

    # add ltable output attributes
    if l_out_attrs_indices:
        for l_attr_index in l_out_attrs_indices:
            output_row.append(l_row[l_attr_index])

    # add rtable output attributes
    if r_out_attrs_indices:
        for r_attr_index in r_out_attrs_indices:
            output_row.append(r_row[r_attr_index])

    return output_row def remove_redundant_attrs(out_attrs, key_attr):
    # this method removes key_attr from out_attrs, if present.
    # further it removes redundant attributes in out_attrs, 
    # but preserves the order of attributes.
    if out_attrs is None:
        return out_attrs

    uniq_attrs = []
    seen_attrs = {}
    for attr in out_attrs:
        if attr == key_attr or seen_attrs.get(attr) is not None:
            continue
        uniq_attrs.append(attr)
        seen_attrs[attr] = True

    return uniq_attrs def split_table(table, num_splits):
    splits = []
    split_size = 1.0/num_splits*len(table)
    for i in xrange(num_splits):
        splits.append(table[int(round(i*split_size)):
                            int(round((i+1)*split_size))])
    return splits def get_pairs_with_missing_value(ltable, rtable,
                                 l_key_attr, r_key_attr,
                                 l_join_attr, r_join_attr,
                                 l_out_attrs=None, r_out_attrs=None,
                                 l_out_prefix='l_', r_out_prefix='r_',
                                 out_sim_score=False, show_progress=True):
    # find column indices of key attr, join attr and output attrs in ltable
    l_columns = list(ltable.columns.values)
    l_key_attr_index = l_columns.index(l_key_attr)
    l_join_attr_index = l_columns.index(l_join_attr)
    l_out_attrs_indices = find_output_attribute_indices(l_columns, l_out_attrs)

    # find column indices of key attr, join attr and output attrs in rtable
    r_columns = list(rtable.columns.values)
    r_key_attr_index = r_columns.index(r_key_attr)
    r_join_attr_index = r_columns.index(r_join_attr)
    r_out_attrs_indices = find_output_attribute_indices(r_columns, r_out_attrs)
   
    # find ltable records with missing value in l_join_attr
    ltable_missing = ltable[pd.isnull(ltable[l_join_attr])]

    # find ltable records which do not contain missing value in l_join_attr
    ltable_not_missing = ltable[pd.notnull(ltable[l_join_attr])]

    # find rtable records with missing value in r_join_attr
    rtable_missing = rtable[pd.isnull(rtable[r_join_attr])]

    output_rows = []
    has_output_attributes = (l_out_attrs is not None or
                             r_out_attrs is not None)

    if show_progress:
        print('Finding pairs with missing value...')
        prog_bar = pyprind.ProgBar(len(ltable_missing) + len(rtable_missing))

    # For each ltable record with missing value in l_join_attr,
    # output a pair corresponding to every record in rtable.
    for l_row in ltable_missing.itertuples(index=False):
        for r_row in rtable.itertuples(index=False):
            if has_output_attributes:
                output_row = get_output_row_from_tables(
                                 l_row, r_row,
                                 l_key_attr_index, r_key_attr_index,
                                 l_out_attrs_indices, r_out_attrs_indices)
            else:
                output_row = [l_row[l_key_attr_index], r_row[r_key_attr_index]]
            output_rows.append(output_row)

        if show_progress:
            prog_bar.update()

    # For each rtable record with missing value in r_join_attr,
    # output a pair corresponding to every record in ltable which 
    # doesn't have a missing value in l_join_attr.
    for r_row in rtable_missing.itertuples(index=False):
        for l_row in ltable_not_missing.itertuples(index=False):
            if has_output_attributes:
                output_row = get_output_row_from_tables(
                                 l_row, r_row,
                                 l_key_attr_index, r_key_attr_index,
                                 l_out_attrs_indices, r_out_attrs_indices)
            else:
                output_row = [l_row[l_key_attr_index], r_row[r_key_attr_index]]

            if out_sim_score:
                output_row.append(np.NaN)

            output_rows.append(output_row)

        if show_progress:
            prog_bar.update()

    output_header = get_output_header_from_tables(
                        l_key_attr, r_key_attr,
                        l_out_attrs, r_out_attrs,
                        l_out_prefix, r_out_prefix)

    if out_sim_score:
        output_header.append("_sim_score")

    # generate a dataframe from the list of output rows
    output_table = pd.DataFrame(output_rows, columns=output_header)
    return output_table     def gen_token_ordering_for_lists(token_lists):
    token_freq_dict = {}
    for token_list in token_lists:
        for token in token_list:
            token_freq_dict[token] = token_freq_dict.get(token, 0) + 1
            order_idx = 1

    ordered_tokens = sorted(list(token_freq_dict.items()), key=itemgetter(0))

    token_ordering = {}
    for token_freq_tuple in sorted(ordered_tokens, key=itemgetter(1)):
        token_ordering[token_freq_tuple[0]] = order_idx
        order_idx += 1

    return token_ordering def gen_token_ordering_for_tables(table_list, attr_list, tokenizer,
                                  sim_measure_type='OVERLAP'):
    token_freq_dict = {}
    table_index = 0
    for table in table_list:
        for row in table:
            for token in tokenizer.tokenize(row[attr_list[table_index]]):
                token_freq_dict[token] = token_freq_dict.get(token, 0) + 1
        table_index += 1

    ordered_tokens = sorted(list(token_freq_dict.items()), key=itemgetter(0))

    token_ordering = {}
    order_idx = 1
    for token_freq_tuple in sorted(ordered_tokens, key=itemgetter(1)):
        token_ordering[token_freq_tuple[0]] = order_idx
        order_idx += 1

    return token_ordering def order_using_token_ordering(tokens, token_ordering):
    ordered_tokens = []

    for token in tokens:
        order = token_ordering.get(token)
        if order is not None:
            ordered_tokens.append(order)
            
    ordered_tokens.sort()

    return ordered_tokens def validate_attr(attr, table_cols, attr_label, table_label):
    """Check if the attribute exists in the table."""
    if attr not in table_cols:
        raise AssertionError(attr_label + ' \'' + attr + '\' not found in ' + \
                             table_label) 
    return True def validate_attr_type(attr, attr_type, attr_label, table_label):
    """Check if the attribute is not of numeric type."""
    if attr_type != np.object:
        raise AssertionError(attr_label + ' \'' + attr + '\' in ' + 
                             table_label + ' is not of string type.')
    return True def validate_key_attr(key_attr, table, table_label):
    """Check if the attribute is a valid key attribute."""
    unique_flag = len(table[key_attr].unique()) == len(table)
    nan_flag = sum(table[key_attr].isnull()) == 0 
    if not (unique_flag and nan_flag):
        raise AssertionError('\'' + key_attr + '\' is not a key attribute ' + \
                             'in ' + table_label)
    return True def validate_input_table(table, table_label):
    """Check if the input table is a dataframe."""
    if not isinstance(table, pd.DataFrame):
        raise TypeError(table_label + ' is not a dataframe')
    return True def validate_threshold(threshold, sim_measure_type):
    """Check if the threshold is valid for the sim_measure_type."""
    if sim_measure_type == 'EDIT_DISTANCE':
        if threshold < 0:
            raise AssertionError('threshold for ' + sim_measure_type + \
                                 ' should be greater than or equal to 0')
    elif sim_measure_type == 'OVERLAP':
        if threshold <= 0:
            raise AssertionError('threshold for ' + sim_measure_type + \
                                 ' should be greater than 0')
    else:
        if threshold <= 0 or threshold > 1:
            raise AssertionError('threshold for ' + sim_measure_type + \
                                 ' should be in (0, 1]')
    return True def validate_tokenizer_for_sim_measure(tokenizer, sim_measure_type):
    """Check if the tokenizer is valid for the similarity measure.
    """
    if not isinstance(tokenizer, Tokenizer):
        raise TypeError('Invalid tokenizer provided as input')

    if sim_measure_type == 'EDIT_DISTANCE':
        if not isinstance(tokenizer, QgramTokenizer):
            raise AssertionError('Invalid tokenizer for EDIT_DISTANCE ' + \
            'measure. Only qgram tokenizer should be used for EDIT_DISTANCE.')

    return True def validate_output_attrs(l_out_attrs, l_columns, r_out_attrs, r_columns):
    """Check if the output attributes exist in the original tables."""
    if l_out_attrs:
        for attr in l_out_attrs:
            if attr not in l_columns:
                raise AssertionError('output attribute \'' + attr + \
                                     '\' not found in left table')

    if r_out_attrs:
        for attr in r_out_attrs:
            if attr not in r_columns:
                raise AssertionError('output attribute \'' + attr + \
                                     '\' not found in right table')
    return True def validate_sim_measure_type(sim_measure_type):
    """Check if the input sim_measure_type is one of the supported types."""
    sim_measure_types = ['COSINE', 'DICE', 'EDIT_DISTANCE', 'JACCARD',
                         'OVERLAP']
    if sim_measure_type.upper() not in sim_measure_types:
        raise TypeError('\'' + sim_measure_type + '\' is not a valid ' + \
                        'sim_measure_type. Supported types are COSINE, DICE' + \
                        ', EDIT_DISTANCE, JACCARD and OVERLAP.')
    return True
from joblib import delayed, Parallel
from six import iteritems
from six.moves import xrange
from py_stringsimjoin.filter.filter import Filter
from py_stringsimjoin.filter.filter_utils import get_overlap_threshold, \
    get_prefix_length, get_size_lower_bound, get_size_upper_bound
from py_stringsimjoin.index.position_index import PositionIndex
from py_stringsimjoin.utils.generic_helper import convert_dataframe_to_array, \
    find_output_attribute_indices, get_attrs_to_project, \
    get_num_processes_to_launch, get_output_header_from_tables, \
    get_output_row_from_tables, remove_redundant_attrs, split_table
from py_stringsimjoin.utils.missing_value_handler import \
    get_pairs_with_missing_value
from py_stringsimjoin.utils.token_ordering import gen_token_ordering_for_lists,\
    gen_token_ordering_for_tables, order_using_token_ordering
from py_stringsimjoin.utils.validation import validate_attr, \
    validate_attr_type, validate_key_attr, validate_input_table, \
    validate_threshold, validate_tokenizer_for_sim_measure, \
    validate_output_attrs, validate_sim_measure_type
import pandas as pd
import pyprind
        """

        # If one of the inputs is missing, then check the allow_missing flag.
        # If it is set to True, then pass the pair. Else drop the pair.
        if pd.isnull(lstring) or pd.isnull(rstring):
            return (not self.allow_missing)

        # tokenize input strings     
        ltokens = self.tokenizer.tokenize(lstring)
        rtokens = self.tokenizer.tokenize(rstring)

        l_num_tokens = len(ltokens)
        r_num_tokens = len(rtokens)

        if l_num_tokens == 0 and r_num_tokens == 0:
            if self.sim_measure_type == 'OVERLAP':
                return True
            elif self.sim_measure_type == 'EDIT_DISTANCE':
                return False
            else:
                return (not self.allow_empty)

        token_ordering = gen_token_ordering_for_lists([ltokens, rtokens])
        ordered_ltokens = order_using_token_ordering(ltokens, token_ordering)
        ordered_rtokens = order_using_token_ordering(rtokens, token_ordering)

        l_prefix_length = get_prefix_length(l_num_tokens,
                                            self.sim_measure_type,
                                            self.threshold,
                                            self.tokenizer) 
        r_prefix_length = get_prefix_length(r_num_tokens,
                                            self.sim_measure_type,
                                            self.threshold,
                                            self.tokenizer)

        if l_prefix_length <= 0 or r_prefix_length <= 0:
            return True
 
        l_prefix_dict = {}
        l_pos = 0
        for token in ordered_ltokens[0:l_prefix_length]:
            l_prefix_dict[token] = l_pos

        overlap_threshold = get_overlap_threshold(l_num_tokens, r_num_tokens,
                                                  self.sim_measure_type,
                                                  self.threshold,
                                                  self.tokenizer)
        current_overlap = 0
        r_pos = 0 
        for token in ordered_rtokens[0:r_prefix_length]:
            l_pos = l_prefix_dict.get(token)
            if l_pos is not None:
                overlap_upper_bound = 1 + min(l_num_tokens - l_pos - 1,
                                              r_num_tokens - r_pos - 1)
                if (current_overlap + overlap_upper_bound) < overlap_threshold:
                    return True
                current_overlap += 1
            r_pos += 1

        if current_overlap > 0:
            return False
        return True
        
    def filter_tables(self, ltable, rtable,
                      l_key_attr, r_key_attr,
                      l_filter_attr, r_filter_attr,
                      l_out_attrs=None, r_out_attrs=None,
                      l_out_prefix='l_', r_out_prefix='r_',
                      n_jobs=1, show_progress=True):
        """Finds candidate matching pairs of strings from the input tables using
        position filtering technique.

        Args:
            ltable (DataFrame): left input table.

            rtable (DataFrame): right input table.

            l_key_attr (string): key attribute in left table.

            r_key_attr (string): key attribute in right table.

            l_filter_attr (string): attribute in left table on which the filter 
                should be applied.                                              
                                                                                
            r_filter_attr (string): attribute in right table on which the filter
                should be applied.                                              
                                                                                
            l_out_attrs (list): list of attribute names from the left table to  
                be included in the output table (defaults to None).             
                                                                                
            r_out_attrs (list): list of attribute names from the right table to 
                be included in the output table (defaults to None).             
                                                                                
            l_out_prefix (string): prefix to be used for the attribute names    
                coming from the left table, in the output table                 
                (defaults to 'l\_').                                            
                                                                                
            r_out_prefix (string): prefix to be used for the attribute names    
                coming from the right table, in the output table                
                (defaults to 'r\_').                                            

            n_jobs (int): number of parallel jobs to use for the computation    
                (defaults to 1). If -1 is given, all CPUs are used. If 1 is     
                given, no parallel computing code is used at all, which is      
                useful for debugging. For n_jobs below -1,                      
                (n_cpus + 1 + n_jobs) are used (where n_cpus is the total       
                number of CPUs in the machine). Thus for n_jobs = -2, all CPUs  
                but one are used. If (n_cpus + 1 + n_jobs) becomes less than 1, 
                then no parallel computing code will be used (i.e., equivalent  
                to the default).                                                                                
                                                                                
            show_progress (boolean): flag to indicate whether task progress     
                should be displayed to the user (defaults to True).             
                                                                                
        Returns:                                                                
            An output table containing tuple pairs that survive the filter      
            (DataFrame).
        """

        # check if the input tables are dataframes

        validate_input_table(ltable, 'left table')