1
$\begingroup$

I wanna clean a Persian text from stop-words. I already have stop-word data that is provided on the below link. It seems to me, if I have a pre-built tree on stop-words, I could save lots of time. I want to search each word of text in this pre-built tree, if the word is in the tree I delete it from the text, if not I hold it.

O(n * l) to O(n*log(l)).

This is my stop-words

If you have better suggestions than the pre-built tree search, I would be grateful to share it with me.

$\endgroup$
1
$\begingroup$

This is an answer with tire tree:

readindg data:

#readindg stopword data
stopwords = pd.read_csv('STOPWORDS',header=None)

tire tree:

#creating tire tree
class TrieNode: 

    # Trie node class 
    def __init__(self): 
        self.children = [None]*15000

        # isEndOfWord is True if node represent the end of the word 
        self.isEndOfWord = False

class Trie: 

    # Trie data structure class 
    def __init__(self): 
        self.root = self.getNode() 

    def getNode(self): 

        # Returns new trie node (initialized to NULLs) 
        return TrieNode() 

    def _charToIndex(self,ch): 

        # private helper function 
        # Converts key current character into index 
        # use only 'a' through 'z' and lower case 

        return ord(ch)-ord('!') 


    def insert(self,key): 

        # If not present, inserts key into trie 
        # If the key is prefix of trie node, 
        # just marks leaf node 
        pCrawl = self.root 
        length = len(key) 
        for level in range(length): 
            index = self._charToIndex(key[level]) 

            # if current character is not present 
            if not pCrawl.children[index]: 
                pCrawl.children[index] = self.getNode() 
            pCrawl = pCrawl.children[index] 

        # mark last node as leaf 
        pCrawl.isEndOfWord = True

    def search(self, key): 

        # Search key in the trie 
        # Returns true if key presents 
        # in trie, else false 
        pCrawl = self.root 
        length = len(key) 
        for level in range(length): 
            index = self._charToIndex(key[level]) 
            if not pCrawl.children[index]: 
                return False
            pCrawl = pCrawl.children[index] 

        return pCrawl != None and pCrawl.isEndOfWord 

Example of use:

# Input keys (use only 'a' through 'z' and lower case) 
keys = list(stopwords.loc[:,0])

output = ["Not present in trie", 
        "Present in trie"] 

# Trie object 
t = Trie() 

# Construct trie 
for key in keys: 
    t.insert(key) 


print("{} ---- {}".format("از",output[t.search("از")])) 

Output:

از ---- Present in trie
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.