current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 2 down vote favorite

I am trying to find a way to enhance a filtering algorithm. I am developing a backup software that enables users to specify custom filters to exclude unwanted files/directories. Currently when trying to check if a file should be taken into backup, the path of the file is compared against a list of rules.

Each rule is specific to a single path (file or directory) and the path of the file is compared in a way similar to this:

Lets assume this is our rule structure

[Rule]
Path = "C:\Windows\"
Exclude = TRUE

And I compare the file path I got with the rule path by the length of the rule path.

Now, this works fine and I haven't had an issue with it but my issue is that I do not have a limit on the number of rules a user can add to the system. He can add as many rules as he likes and here is my problem.

The more rules a user adds means more iterations for each file against the rules set.

What is a good practice to do such thing?

share|improve this question

1 Answer 1

up vote 3 down vote

One way to improve this is to build a tree structure out of the path components.

So if he adds c:\Windows\system32 and c:\Windows\temp and your input path is c:\users\serpent then you can happily skip both rules with a single check.

As your rule set gets bigger, this approach can reduce the amount of checking considerably. Some collections can do this for you automatically (a c++ stl map for example), you add all your paths and the collection stores them in a tree structure based on the strings.

Edit:

imagine you're looking for a taxi in the phone directory. Do you: start at the beginning and work your way through, comparing you input requirement of a taxi against the aardvark trainers, then the abacus sellers, etc; or do you skip to the T section, then skip to the Taxi subsection and then look through the list of taxi companies?

This is the same principle - if you split your rule paths into their components, then an input directory that is (in our examples) not inside the Windows root directory can be skipped completely - there's no need to check against c:\Windows\temp because you've ruled out all c:\Windows\everything rules.

share|improve this answer
    
Sorry but I do not understand how a map or tree can help me with this. not that I am comparing files agains a set of files and/or directories. For example, if the input path is lets say c:\Windows\temp\somedirectoy\somefile and the rule is c:\Windows\temp how will I check this since the file path nor its immediate parent is present in the collection. –  Red Serpent Feb 25 at 11:56
    
c:\Windows\temp marks the path from the root. Every subpath is ruled out. Since c:\Windows\temp\somedirectoy is a subpath it is ruled out. You have to construct two pathobjects and do the comparison. –  Thomas Junk Feb 25 at 12:05
    
@RedSerpent You could store the rules in a trie. If the input path is C:\Windows\Temp\somedirectory\somefile you'd traverse the trie going down the C: branch, then the Windows branch, and finally the Temp branch (where presumably the search ends, if there's no rules for subdirectories of Temp). Depending on how rule precedence works you may look at the rules at each node along the way (if e.g. the rules for C:, C:\Windows and C:\Windows\Temp stack) or look at only the rules at the end (if the rules for C:\Windows\Temp take precedence.). –  Doval Feb 25 at 15:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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