string - सवर - पैटर्न लॉक रिसेट




तारों की सूचियों/सरणियों में समान पैटर्न कैसे प्राप्त करें (6)

मैं सूचियों या स्ट्रिंग्स के मिलान पैटर्न को विशेष रूप से .net में मिलान करने वाले तरीके ढूंढने के तरीकों की तलाश कर रहा हूं, लेकिन अन्य भाषाओं के एल्गोरिदम या तर्क मददगार होगा।

कहें कि मेरे पास 3 एरे हैं (या इस विशेष मामले की सूची में (स्ट्रिंग की))

Array1
"Do"
"Re"
"Mi"
"Fa"
"So"
"La"
"Ti"

Array2
"Mi"
"Fa"
"Jim"
"Bob"
"So"

Array3
"Jim"
"Bob"
"So"
"La"
"Ti"

मैं मैचों की घटनाओं की रिपोर्ट करना चाहता हूं

("Mi", "Fa") In Arrays (1,2)
("So") In Arrays (1,2,3)
("Jim", "Bob", "So") in Arrays (2,3)
("So", "La", "Ti") in Arrays (1, 3)

... और किसी भी अन्य

मैं इसे किसी समस्या का निवारण करने के लिए उपयोग कर रहा हूं, विशेष रूप से इसे का व्यावसायिक उत्पाद बनाने के लिए नहीं, और हाथ से इसे नहीं बल्कि (लगभग 100-200 वस्तुओं की 110 सूचियां हैं)।

क्या कोई एल्गोरिदम, मौजूदा कोड, या विचार हैं जो मुझे बताए गए परिणाम खोजने में मदद करेंगे?


ऐसा लगता है कि आप डेटा के सेट पर एक प्रतिच्छेदन फ़ंक्शन का उपयोग करना चाहते हैं। चौराहे उन तत्वों को उठाती है जो दोनों (या अधिक) सेटों में आम हैं।

इस दृष्टिकोण के साथ समस्या यह है कि सेट में प्रत्येक तत्व में से एक से अधिक नहीं हो सकता है, अर्थात प्रति सेट एक से अधिक जिम नहीं, यह एक पंक्ति के रूप में कई तत्वों को एक पैटर्न के रूप में पहचान नहीं सकता है, फिर भी आप आगे देखने के लिए तुलना फ़ंक्शन को संशोधित कर सकते हैं सिर्फ यह देखने के लिए

वहाँ मेई फ़ंक्शन की तरह काम करती है जो बैगों पर काम करती है (जो सेट की तरह होती है, लेकिन समान तत्वों को सहन करती है)।

ये कार्य अधिकतर भाषाओं में मानक होना चाहिए या खुद को लिखना बहुत आसान है।


कोड का सबसे सरल तरीका प्रत्येक सरणी में प्रत्येक आइटम के माध्यम से एक शब्दकोश तब लूप का निर्माण करना होगा। प्रत्येक आइटम के लिए ऐसा करें:

जाँच करें कि आइटम को आदेश में है यदि ऐसा है तो सूची को सरणी में जोड़ें। यदि आइटम डिक्शनरी में नहीं है और उसे सूची में जोड़ें

चूंकि आपने यह कहा है कि यह गैर-उत्पादन कोड प्रदर्शन है, इससे कोई फर्क नहीं पड़ता है इसलिए इस दृष्टिकोण को ठीक काम करना चाहिए।


मुझे यकीन है कि वहाँ बहुत अधिक सुरुचिपूर्ण तरीका है, लेकिन ...

चूंकि यह उत्पादन कोड नहीं है, इसलिए केवल उसे हैक न करें और प्रत्येक सरणी को एक सीमांकित स्ट्रिंग में परिवर्तित करें, फिर आप जो पैटर्न चाहते हैं, उसके लिए प्रत्येक स्ट्रिंग खोजिए? अर्थात


        private void button1_Click(object sender, EventArgs e)
        {

            string[] array1 = { "do", "re", "mi", "fa", "so" };
            string[] array2 = { "mi", "fa", "jim", "bob", "so" };
            string[] pattern1 = { "mi", "fa" };
            MessageBox.Show(FindPatternInArray(array1, pattern1).ToString());
            MessageBox.Show(FindPatternInArray(array2, pattern1).ToString());

        }

        private bool FindPatternInArray(string[] AArray, string[] APattern)
        {
            return string.Join("~", AArray).IndexOf(string.Join("~", APattern)) >= 0;
        }

मैंने पर्ल के बारे में 10 मिनट में कार्यक्रम काट दिया। यह सही नहीं है, यह एक वैश्विक चर का उपयोग करता है, और यह प्रत्येक सूची में कार्यक्रम द्वारा देखा जाने वाला प्रत्येक तत्व की गणना करता है, लेकिन यह एक अच्छा अनुमान है कि आप क्या करना चाहते हैं जो कि कोड के सुपर-आसान है

क्या आप वास्तव में प्रत्येक सरणी के लिए सामान्य तत्वों के सभी उपसमुच्चय के सभी संयोजन चाहते हैं? अगर आप चाहते थे कि आप सभी तत्वों को चालाक तरीके से बता सकते हैं, लेकिन यदि आप चाहते हैं कि प्रत्येक तत्व में कम से कम एक बार मौजूद सभी तत्व आप नीचे दिए गए आउटपुट पर यूनिक्स कमांड "grep -v 0" का उपयोग कर सकें आप सभी तत्वों का अंतरालन सभी सरणियों के लिए आम है। आपके प्रश्न में थोड़ा विस्तार नहीं है, इसलिए मैं पूरी तरह से कुछ को लागू नहीं कर सकता जो आपकी समस्या का समाधान करता है

यदि आप प्रोग्रामिंग की तुलना में अधिक डेटा विश्लेषण करते हैं, तो इस तरह से पाठ डेटा से सवाल पूछने के लिए पटकथा बहुत उपयोगी हो सकती है। अगर आपको नहीं पता कि इस तरह एक पटकथा भाषा में कोड कैसे होगा, तो मैं एक महीने या दो बार पढ़ने के बारे में बताऊंगा कि कैसे पर्ल, पायथन या रूबी में कोड वे इस तरह के एक बंद हैक्स के लिए अद्भुत हो सकते हैं, विशेष रूप से उन मामलों में जब आप वास्तव में नहीं जानते कि आप क्या चाहते हैं। इस तरह से एक प्रोग्राम लिखने का समय और मस्तिष्क की लागत वास्तव में कम है, इसलिए (यदि आप तेज़ी से हैं) तो आप अपने प्रश्न की परिभाषा की खोज करते हुए इसे कई बार लिख सकते हैं और फिर से लिख सकते हैं।

#!/usr/bin/perl -w

use strict;

my @Array1 = ( "Do", "Re", "Mi", "Fa", "So", "La", "Ti");
my @Array2 = ( "Mi", "Fa", "Jim", "Bob", "So" );
my @Array3 = ( "Jim", "Bob", "So", "La", "Ti" );

my %counts;
sub count_array {
    my $array = shift;
    my $name  = shift;
    foreach my $e (@$array) {
        $counts{$e}{$name}++;
    }
}

count_array( \@Array1, "Array1" );
count_array( \@Array2, "Array2" );
count_array( \@Array3, "Array3" );

my @names = qw/ Array1 Array2 Array3 /;
print join ' ', ('element',@names);
print "\n";

my @unique_names = keys %counts;
foreach my $unique_name (@unique_names) {
    my @counts = map {
        if ( exists $counts{$unique_name}{$_} ) {
            $counts{$unique_name}{$_};
        } else {
            0;
        }
    }
    @names;

    print join ' ', ($unique_name,@counts);
    print "\n";
}

प्रोग्राम का आउटपुट है:

element Array1 Array2 Array3
Ti 1 0 1
La 1 0 1
So 1 1 1
Mi 1 1 0
Fa 1 1 0
Do 1 0 0
Bob 0 1 1
Jim 0 1 1
Re 1 0 0

मान लें कि एक पासवर्ड में अंग्रेजी वर्णमाला (26 वर्णों) से नौ अक्षर की एक स्ट्रिंग शामिल है। यदि प्रत्येक संभावित पासवर्ड को मिलीसेकंड में जांच किया जा सकता है, तो सभी संभावित पासवर्डों को जांचने में कितना समय लगेगा?


यहाँ स्थितियों का पता लगाने के लिए प्रोफ़िक्सट्री मॉड्यूल का उपयोग कर एक समाधान है:

#!/usr/bin/env python
from SuffixTree  import SubstringDict
from collections import defaultdict
from itertools   import groupby
from operator    import itemgetter
import sys

def main(stdout=sys.stdout):
    """
    >>> import StringIO
    >>> s = StringIO.StringIO()
    >>> main(stdout=s)
    >>> print s.getvalue()
    [['Mi', 'Fa']] In Arrays (1, 2)
    [['So', 'La', 'Ti']] In Arrays (1, 3)
    [['Jim', 'Bob', 'So']] In Arrays (2, 3)
    [['So']] In Arrays (1, 2, 3)
    <BLANKLINE>
    """
    # array of arrays of strings
    arr = [
        ["Do", "Re", "Mi", "Fa", "So", "La", "Ti",],
        ["Mi", "Fa", "Jim", "Bob", "So",],
        ["Jim", "Bob", "So", "La", "Ti",],
    ]

####    # 28 seconds  (27 seconds without lesser substrs inspection (see below))
####    N, M = 100, 100
####    import random
####    arr = [[random.randrange(100) for _ in range(M)] for _ in range(N)]

    # convert to ASCII alphabet (for SubstringDict)
    letter2item = {}
    item2letter = {}
    c = 1
    for item in (i for a in arr for i in a):
        if item not in item2letter:
            c += 1
            if c == 128:
                raise ValueError("too many unique items; "
                                 "use a less restrictive alphabet for SuffixTree")
            letter = chr(c)
            letter2item[letter] = item
            item2letter[item] = letter
    arr_ascii = [''.join(item2letter[item] for item in a) for a in arr]

    # populate substring dict (based on SuffixTree)
    substring_dict = SubstringDict()
    for i, s in enumerate(arr_ascii):
        substring_dict[s] = i+1

    # enumerate all substrings, save those that occur more than once
    substr2indices = {}
    indices2substr = defaultdict(list)
    for str_ in arr_ascii:
        for start in range(len(str_)):
            for size in reversed(range(1, len(str_) - start + 1)):
                substr = str_[start:start + size]
                if substr not in substr2indices:
                    indices = substring_dict[substr] # O(n) SuffixTree
                    if len(indices) > 1:
                        substr2indices[substr] = indices
                        indices2substr[tuple(indices)].append(substr)
####                        # inspect all lesser substrs
####                        # it could diminish size of indices2substr[ind] list
####                        # but it has no effect for input 100x100x100 (see above)
####                        for i in reversed(range(len(substr))):
####                            s = substr[:i]
####                            if s in substr2indices: continue
####                            ind = substring_dict[s]
####                            if len(ind) > len(indices):
####                                substr2indices[s] = ind
####                                indices2substr[tuple(ind)].append(s)
####                                indices = ind
####                            else:
####                                assert set(ind) == set(indices), (ind, indices)
####                                substr2indices[s] = None
####                        break # all sizes inspected, move to next `start`

    for indices, substrs in indices2substr.iteritems():
        # remove substrs that are substrs of other substrs
        substrs = sorted(substrs, key=len) # sort by size
        substrs = [p for i, p in enumerate(substrs)
                   if not any(p in q  for q in substrs[i+1:])]
        # convert letters to items and print
        items = [map(letter2item.get, substr) for substr in substrs]
        print >>stdout, "%s In Arrays %s" % (items, indices)

if __name__=="__main__":
    # test
    import doctest; doctest.testmod()
    # measure performance
    import timeit
    t = timeit.Timer(stmt='main(stdout=s)',
                     setup='from __main__ import main; from cStringIO import StringIO as S; s = S()')
    N = 1000
    milliseconds = min(t.repeat(repeat=3, number=N))
    print("%.3g milliseconds" % (1e3*milliseconds/N))

प्रत्येक 100 आइटमों की 100 सूचियों को संसाधित करने में लगभग 30 सेकंड लगते हैं। उपरोक्त कोड में SubstringDict को grep -F -f द्वारा अनुकरण किया जा सकता है

पुराने समाधान:

पायथन में (इसे 'group_patterns.py' फ़ाइल में सहेजें):

#!/usr/bin/env python
from collections import defaultdict
from itertools   import groupby

def issubseq(p, q):
    """Return whether `p` is a subsequence of `q`."""
    return any(p == q[i:i + len(p)] for i in range(len(q) - len(p) + 1))

arr = (("Do", "Re", "Mi", "Fa", "So", "La", "Ti",),
       ("Mi", "Fa", "Jim", "Bob", "So",),
       ("Jim", "Bob", "So", "La", "Ti",))

# store all patterns that occure at least twice
d = defaultdict(list) # a map: pattern -> indexes of arrays it's within
for i, a in enumerate(arr[:-1]):
    for j, q in enumerate(arr[i+1:]): 
        for k in range(len(a)):
            for size in range(1, len(a)+1-k):
                p = a[k:k + size] # a pattern
                if issubseq(p, q): # `p` occures at least twice
                    d[p] += [i+1, i+2+j]

# group patterns by arrays they are within
inarrays = lambda pair: sorted(set(pair[1]))
for key, group in groupby(sorted(d.iteritems(), key=inarrays), key=inarrays):
    patterns = sorted((pair[0] for pair in group), key=len) # sort by size
    # remove patterns that are subsequences of other patterns
    patterns = [p for i, p in enumerate(patterns)
                if not any(issubseq(p, q)  for q in patterns[i+1:])]
    print "%s In Arrays %s" % (patterns, key)

निम्न कमांड:

$ python group_patterns.py

प्रिंट:

[('Mi', 'Fa')] In Arrays [1, 2]
[('So',)] In Arrays [1, 2, 3]
[('So', 'La', 'Ti')] In Arrays [1, 3]
[('Jim', 'Bob', 'So')] In Arrays [2, 3]

समाधान बहुत ही अक्षम है।








pattern-matching