Python Forum
Thread Rating:
  • 2 Vote(s) - 2 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Find closest string pattern
#1
I need a way to identify the closest matching list based on the string based on the sequence of words.

for example.
my_list = ['one', 'two', 'three' , 'four']

option_one = ['two', 'three', 'one', 'four']
option_two = ['four', 'three', 'two', 'one']

The closest sequence of the two options to my_list is option_one. The order of the positions are not the same as my_list but they are closer than option_two.
edit: to clarify, I'm looking for the closest match reading left to right in sequence. Though it doesn't equal my_list, it closer that option_two.

And that's about where my brain stops. I'm not sure of an elegant way to solve this. I'm not looking for a coded solution, but if anyone has an idea on how to go about solving it, I'm all ears.

Thanks!
Reply
#2
"closest matching list" seems undefined here. Is this homework, where you have thorough instructions, or is the requirement coming from somewhere else?
Reply
#3
How do you know option_one is closer? You can't put that into code before you can put it into words.
Reply
#4
(Dec-12-2018, 07:37 PM)nilamo Wrote: How do you know option_one is closer? You can't put that into code before you can put it into words.

Though the string values don't line up exactly with my_list, the sequence is closer reading from left to right than option two.
Reply
#5
Every element of option_two is only one element away from my_list. option_one's "one" is two elements away. So why isn't option_two the closer match?
Reply
#6
(Dec-12-2018, 07:09 PM)micseydel Wrote: "closest matching list" seems undefined here. Is this homework, where you have thorough instructions, or is the requirement coming from somewhere else?
nah, not homework. I was listening to a lecture about NLP and the difference between identifying words in a string, identifying the sequence of words in a string and intent. It just had me wondering how to find the closest matching sentence based on matching word order from left to right.
ie.
my_string = "I that the dead beat cat"

option_one = "Is the cat dead"
option_two = "I beat the dead cat"

both contain some/all of the words as my_string. But one is closer to matching my_string on the sequence of words from left to right.
Reply
#7
You could use a metric similar to the edit distance, ie the minimal number of operations required to transform one list into another.
Reply
#8
(Dec-12-2018, 07:52 PM)nilamo Wrote: Every element of option_two is only one element away from my_list. option_one's "one" is two elements away. So why isn't option_two the closer match?

thank you for that perspective. I added an edit to help clarify that.

my_list = red, red, red, blue, black
option1 = blue, red
option2 = red, black

option2 shares the closest order as my_list reading left to right.
Reply
#9
Using the normalized compression distance, option 1 is better in the first example and option 2 is better in the second example
from zlib import compress

def ncd(a, b):
    """Normalized compression distance between two byte strings"""
    u =len(compress(a))
    v =len(compress(b))
    u, v =min(u, v), max (u, v)
    w =len(compress(a + b))
    return float (w - u) / v 

def l2b(alist):
    return ",".join(alist).encode()

def option_distances(alist, *options):
    b = l2b(alist)
    return [(ncd(b, l2b(option)), option)
            for option in options]


if __name__ == '__main__':
    my_list = ['one', 'two', 'three' , 'four']
    option_one = ['two', 'three', 'one', 'four']
    option_two = ['four', 'three', 'two', 'one']
    
    print(my_list)
    for d, option in option_distances(my_list, option_one, option_two):
        print(d, option)
    
    my_list = "red red red blue black".split()
    option1 = "blue red".split()
    option2 = "red black".split()
    
    print(my_list)
    for d, option in option_distances(my_list, option1, option2):
        print(d, option)
Output:
['one', 'two', 'three', 'four'] 0.19230769230769232 ['two', 'three', 'one', 'four'] 0.3076923076923077 ['four', 'three', 'two', 'one'] ['red', 'red', 'red', 'blue', 'black'] 0.43478260869565216 ['blue', 'red'] 0.391304347826087 ['red', 'black']
Reply
#10
(Dec-12-2018, 08:54 PM)Gribouillis Wrote: Using the normalized compression distance, option 1 is better in the first example and option 2 is better in the second example
from zlib import compress

def ncd(a, b):
    """Normalized compression distance between two byte strings"""
    u =len(compress(a))
    v =len(compress(b))
    u, v =min(u, v), max (u, v)
    w =len(compress(a + b))
    return float (w - u) / v 

def l2b(alist):
    return ",".join(alist).encode()

def option_distances(alist, *options):
    b = l2b(alist)
    return [(ncd(b, l2b(option)), option)
            for option in options]


if __name__ == '__main__':
    my_list = ['one', 'two', 'three' , 'four']
    option_one = ['two', 'three', 'one', 'four']
    option_two = ['four', 'three', 'two', 'one']
    
    print(my_list)
    for d, option in option_distances(my_list, option_one, option_two):
        print(d, option)
    
    my_list = "red red red blue black".split()
    option1 = "blue red".split()
    option2 = "red black".split()
    
    print(my_list)
    for d, option in option_distances(my_list, option1, option2):
        print(d, option)
Output:
['one', 'two', 'three', 'four'] 0.19230769230769232 ['two', 'three', 'one', 'four'] 0.3076923076923077 ['four', 'three', 'two', 'one'] ['red', 'red', 'red', 'blue', 'black'] 0.43478260869565216 ['blue', 'red'] 0.391304347826087 ['red', 'black']

Perfect, thanks. I'll look at that. Appreciate the direction.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Find and Replace numbers in String giddyhead 2 1,194 Jul-17-2022, 06:22 PM
Last Post: giddyhead
Thumbs Up [SOLVED] Find last occurence of pattern in text file? Winfried 4 4,302 Aug-13-2021, 08:21 PM
Last Post: Winfried
  Find string between two substrings, in a stream of data xbit 1 2,113 May-09-2021, 03:32 PM
Last Post: bowlofred
  Regular expression: cannot find 1st number in a string Pavel_47 2 2,364 Jan-15-2021, 04:39 PM
Last Post: bowlofred
  find a string in a field in MongoDB Leon79 2 2,371 Jul-19-2020, 09:20 PM
Last Post: menator01
  Help to find a string and read the next lines crlamaral 4 2,398 Mar-19-2020, 09:24 AM
Last Post: Larz60+
  How To Find an Opening and Closing String, Copying Open/Close/Contents to New File davidshq 1 1,988 Mar-03-2020, 04:47 AM
Last Post: davidshq
  'Get closest value array in array of arrays.' follow up help. DreamingInsanity 10 7,116 Dec-05-2019, 06:30 PM
Last Post: DreamingInsanity
  Get closest value array for array of arrays. DreamingInsanity 2 2,299 Nov-18-2019, 03:55 PM
Last Post: DreamingInsanity
  finding the closest floating point number in a list Skaperen 17 8,098 Sep-19-2019, 10:39 PM
Last Post: Skaperen

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020