3
\$\begingroup\$

I'm trying to compare every element in a vector with every other.

From a dataframe of addresses, I extract streets for a zip code. And a vector of these street strings (like "123 main avenue") is the input.

streets <- c ("123 main avenue", "123 main ave", "456 paul st", 
              "456 paul street", "1 r parkway", "1 r pkwy")

I want to test for similarity of strings (like the one before with "123 main ave"). I could use string distance on the substrings, but preferred grep.

I want to avoid the nested for loop, but cannot think of anything better. Here's what I am trying to do:

compare = function(postal_code)
{
streets <- as.vector(props[props$Zip == postal_code,]["Street"])    
cnt <- lengths(streets)[1][1]

#Assume two streets "123 main ave" and "123 main avenue"

for (i in 1:cnt)
{
    for (j in 1:cnt)
    {            

    prop1 = streets[[1]][i]
    prop2 = streets[[1]][j]

    #split "123 main avenue" into parts
    prop1_parts = strsplit(trimws(prop1), ' ')
    prop2_parts = strsplit(trimws(prop2), ' ')
    prop1_parts_count = length(prop1_parts[[1]])
    prop2_parts_count = length(prop2_parts[[1]])

    #only if the parts of the two streets are equal 
    if (prop1_parts_count == prop2_parts_count)
        {
            #compare apples to apples: 123 with 123, main with main, and ave with avenue 
           for (x in 1:prop1_parts_count)
            {
                part1 = prop1_parts[[1]][x]
                part2 = prop2_parts[[1]][x]

                if (part1 == part2) { matched = matched & TRUE }
                else {
                    #ignore number parts like 123 
                    if (any(grep("[[:alpha:]]", part1)) & any(grep("[[:alpha:]]", part2))) {
                    #check if avenue is in ave or ave is in avenue
                    if (any(grep(part1, part2)) | any(grep(part2, part1))) {
                            matched = matched & TRUE
                            print(paste0(prop1, '-', prop2))
                        }
                    }
                    else {
                        matched = matched & FALSE
                        break #to pass to the next string
                    }
                }                    
            }
        }
    }
 }             
}

For a vector with 104 streets, the comparisons should be (104*103)/2; but with this code it is 104**2; and for these 10816 comparisons, the benchmark is:

enter image description here

I compiled the function as well but no improvement in the execution time.

Any elegant/quick way to improve this code is appreciated.

\$\endgroup\$
4
\$\begingroup\$

You'd better use another strategy:

  1. Find a table of all usual abbreviations used in postal addresses.
  2. Create a new column normalized_street in your original dataframe by replacing all occurrences of abbreviations in column Street by the corresponding full words.
  3. Perform an exact self-join on your original dataframe, by Zip and normalized_street.

Why I think it's better:

  • It will allow you to avoid false positives like cat street / catfish street
  • The exact self-join will be very efficient
  • Your code will be simpler, cleaner, and entirely vectorized

There are lots of things to say about your current code. I'll just point out a few mistakes so that you can avoid them next time:

  • matched is not initialized
  • as.vector(props[props$Zip == postal_code,]["Street"]) can be written in a simpler way: props[props$Zip == postal_code, "Street"]
  • Since streets is a vector, you get its length using length(streets)
  • For the same reason, you have to use streets[i] instead of streets[[1]][i]
  • You should use grepl() instead of any(grep())
\$\endgroup\$
  • \$\begingroup\$ Thanks for the inputs. Will try the lookup-normalized approach and report back. the initialization of matched to TRUE got cut out :(. Fixed the mistakes you pointed out; exec time was down by 1s; may be with the approach above, it should get optimized. \$\endgroup\$ – skrubber Jul 21 '17 at 20:55

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.