ზელიგ ჰარისი და განაწილებითი ანალიზი

გამოთვლითი სტემინგის სათავეები

1955 წელს ლინგვისტმა ზელიგ ჰარისმა გამოაქვეყნა From Phoneme to Morpheme, სადაც აღწერა სიტყვებში მნიშვნელოვანი ერთეულების (მორფემების) საზღვრების პოვნის მეთოდი.

მისი გაგება განაწილებითი იყო: თუ ინგლისური სიტყვების დიდ კორპუსს დააკვირდებით, ფუძესა & სუფიქსს შორის საზღვარი სტატისტიკური სიგნალის სახით ვლინდება.

მემკვიდრე მრავალფეროვნების მეთოდი

სიტყვის ნებისმიერი პრეფიქსისთვის, დაითვალეთ კორპუსში რამდენი განსხვავებული სიმბოლო მოსდევს მას. ჰარისმა ამას მემკვიდრე მრავალფეროვნება უწოდა.

განიხილეთ პრეფიქსი "work" კორპუსში, რომელიც შეიცავს: worked, worker, working, works, workshop.

"work"-ის შემდეგ შეიძლება მოყვეს ოთხი განსხვავებული სიმბოლო: მრავალფეროვნების მახვილი. ეს მახვილი მორფემის საზღვარს მიუთითებს. ფუძეა work და ყველაფერი მის შემდეგ სუფიქსია.

ეს 1955 წელს რადიკალური იყო. არანაირი ლინგვისტური წესები, არანაირი ლექსიკონი: მხოლოდ დათვლა. ჰარისმა დაამტკიცა, რომ ენის სტრუქტურა განაწილების საშუალებით ვლინდება.

მემკვიდრე მრავალფეროვნების გაგება

ჰარისის მეთოდი ნებისმიერ ენაზე მუშაობს. გრამატიკის ცოდნა არ გჭირდებათ: სტატისტიკა მორფემების საზღვრებს თავად ავლენს.

პრაქტიკაში, წმინდა მემკვიდრე მრავალფეროვნება დიდ კორპუსს და ფრთხილ პიკის გამოვლენას საჭიროებს. შემდგომმა მკვლევარებმა: ლოვინსმა (1968), პორტერმა (1980): მიდგომა წესებზე დაფუძნებული სუფიქსის მოკვეთამდე გაამარტივეს: კორპუსიდან მემკვიდრე მრავალფეროვნების გამოთვლის ნაცვლად, სუფიქსის წესები პირდაპირ დაკოდეს.

დღეს ააგებთ ჰარისის გაგებით შთაგონებულ წესებზე დაფუძნებულ სუფიქს-მოჭრელს. სუფიქსებს პირდაპირ განსაზღვრავთ, შემდეგ სიტყვებიდან მოჭრით. ასე მუშაობს წარმოების სტემერების უმეტესობა.

თქვენი პირველი სუფიქს-მოჭრელი

დავიწყოთ კოდი

მარტივად დავიწყოთ. დაწერეთ ფუნქცია სახელად stem, რომელიც იღებს სიტყვას & მოჭრის ამ სუფიქსებს (ამ თანმიმდევრობით):

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

წესები:

- პირველ რიგში სიტყვა მცირე ასოებად გადაიყვანეთ

- მოჭერით მხოლოდ ერთი სუფიქსი (ზემოთ მოცემული თანმიმდევრობის პირველი შესაბამისი)

- მოჭერით მხოლოდ მაშინ, თუ დარჩენილი ფუძე მინიმუმ 3 სიმბოლოა

- დააბრუნეთ ფუძე

მაგალითი:

def stem(word):
    word = word.lower()
    # your suffix stripping logic here
    return word

გამონაკლისი შემთხვევების დამუშავება

სტემერის გაჭკვიანება

თქვენს ძირითად მოჭრელს პრობლემა აქვს: running → runn & hoping → hop. ორი დახვეწა გვჭირდება:

1. ორმაგი თანხმოვნის გასუფთავება: თუ -ing ან -ed-ის მოჭრა ბოლოში ორმაგ თანხმოვანს ტოვებს (მაგ. runn), ამოიღეთ ბოლო ასო → run

2. ჩუმი e-ს აღდგენა: თუ -ing-ის მოჭრის შემდეგ ფუძე თანხმოვნით მთავრდება (არა ხმოვნით), & ორიგინალს შეიძლება ჩუმი e ჰქონდა (მაგ. hop hoping-იდან), დაამატეთ e უკან → hope

ჩუმი-e წესისთვის მარტივად: თუ -ing-ის მოჭრის შემდეგ ფუძე 3+ სიმბოლოა, თანხმოვნით მთავრდება, & მეორე-ბოლო სიმბოლო ხმოვანია (ნიმუში hop, mak, tak), დაამატეთ e უკან.

ასევე დაამატეთ ეს ახალი სუფიქსები (-ing, -ed, -ly, -s-მდე შეამოწმეთ):

5. -tion (organization → organiza)

6. -ness (happiness → happi)

7. -ment (movement → move)

8. -able (readable → read)

9. -ible (sensible → sens)

განახლებული სუფიქსების პრიორიტეტი: -tion, -ness, -ment, -able, -ible, -ing, -ed, -ly, -s

შეინარჩუნეთ მინიმალური ფუძის სიგრძის წესი: მოჭერით მხოლოდ თუ დარჩენილი ფუძე 3+ სიმბოლოა.

-ies & -ier წესები

მეტი მორფოლოგია

ინგლისურს კიდევ ერთი გავრცელებული ნიმუში აქვს: -y-ით დამთავრებული სიტყვები ფლექსიისას -ies, -ied, ან -ier-ად იცვლება.

დაამატეთ ეს წესები -s & -ed შემოწმებამდე:

- -ies → მოჭერით & დაამატეთ i (babies → babi)

- -ied → მოჭერით & დაამატეთ i (carried → carri)

- -ier → მოჭერით & დაამატეთ i (earlier → earli)

იგივე მინიმალური ფუძის სიგრძის წესი: გარდაქმენით მხოლოდ თუ შედეგი 3+ სიმბოლოა.

რატომ ვტესტავთ?

ტესტირება სავალდებულოა

გაქვთ მოქმედი სტემერი. საიდან იცით, რომ ის სინამდვილეში მუშაობს? ამჟამად რამდენიმე მაგალითს ხელით ახორციელებთ. ეს მასშტაბირებადი არ არის.

პროფესიული პროგრამული უზრუნველყოფა სამ დონის ტესტირებას იყენებს:

Unit ტესტები: ერთ ფუნქციას ცნობილი შეყვანებით & მოსალოდნელი გამომავლებით ცალკე ტესტავს. სწრაფი, მრავლობითი, კონკრეტული.

ინტეგრაციული ტესტები: ამოწმებს, რომ მრავალი კომპონენტი ერთობლივად მუშაობს. სტემერისთვის, ეს ნიშნავს მის ტესტირებას სიტყვების ჯგუფთან & შედეგების თანმიმდევრულობის შემოწმებას.

ფუნქციონალური ტესტები: სისტემას გარედან ტესტავს, ისე, როგორც მომხმარებელი. სტემერისთვის, ეს ნიშნავს რეალური ტექსტის მიწოდებას & შედეგის გადამოწმებას, რომ აზრი ჰქონდეს ნამდვილ გამოყენების შემთხვევაში, მაგ. ძებნაში.

დაწერთ ყველა სამს.

Unit ტესტების წერა

Unit ტესტები

დაწერეთ ფუნქცია სახელად run_unit_tests, რომელიც stem ფუნქციას მინიმუმ 15 სატესტო შემთხვევით ამოწმებს:

1. ძირითადი სუფიქსის მოჭერა: -ing, -ed, -ly, -s-ით დამთავრებული სიტყვები

2. რთული სუფიქსები: -tion, -ness, -ment, -able, -ible

3. Y-ფლექსია: -ies, -ied, -ier

4. გამონაკლისი შემთხვევები: მოკლე სიტყვები, რომლებიც არ უნდა მოიჭრას, სუფიქსის გარეშე სიტყვები, უკვე ფუძის სახის სიტყვები

5. ორმაგი თანხმოვნის გასუფთავება: running → run, sitting → sit

6. ჩუმი-e-ს აღდგენა: hoping → hope

7. რეგისტრის დამოუკიდებლობა: დიდი ასოებიანი შეყვანა მცირე ასოებად უნდა გადაიქცეს

ტესტები ასე სტრუქტურირეთ:

def run_unit_tests():
    tests = [
        ('running', 'run'),
        ('cats', 'cat'),
        # ... at least 15 test cases
    ]
    passed = 0
    failed = 0
    for word, expected in tests:
        result = stem(word)
        if result == expected:
            passed += 1
        else:
            failed += 1
            print(f'FAIL: stem({word}) = {result}, expected {expected}')
    print(f'{passed}/{passed + failed} unit tests passed')
    return failed == 0

ინტეგრაციული ტესტების წერა

ინტეგრაციული ტესტები

Unit ტესტები ცალკეულ შეყვანებს ამოწმებს. ინტეგრაციული ტესტები ამოწმებს, რომ კომპონენტები ერთად სწორად მუშაობს.

სტემერისთვის, ძირითადი ინტეგრაციული თვისებაა თანმიმდევრულობა: ერთი და იგივე სიტყვის ორჯერ სტემირება ერთსა და იმავე შედეგს უნდა იძლეოდეს. & სიტყვებს, რომლებიც ერთ ჯგუფს უნდა მიეკუთვნებოდეს, ერთი და იგივე ფუძე უნდა ქონდეს.

დაწერეთ ფუნქცია სახელად run_integration_tests, რომელიც ამოწმებს:

1. იდემპოტენტურობა: უკვე-სტემირებული სიტყვის სტემირება იგივე ფუძეს უნდა დაბრუნებდეს. stem(stem(word)) == stem(word) ყველა სიტყვისთვის.

2. დაჯგუფება: სიტყვებს, რომლებიც ერთ ფუძეს უნდა იზიარებდეს, ეს სინამდვილეში ისე ხდება. ტესტეთ მინიმუმ 3 სიტყვის ოჯახი (მაგ. run/runs/running/runner ყველამ ფუძე უნდა გაიზიაროს).

3. ჯგუფური დამუშავება: დაამუშავეთ 20+ სიტყვის სია & გადაამოწმეთ, რომ crash-ი, ცარიელი სტრიქონები ან None მნიშვნელობები არ არის.

def run_integration_tests():
    # Test 1: idempotency
    # Test 2: word family grouping
    # Test 3: batch stability
    ...

ფუნქციონალური ტესტების წერა

ფუნქციონალური ტესტები

ფუნქციონალური ტესტები ამოწმებს, რომ სისტემა მის განსაზღვრული გამოყენების შემთხვევისთვის მუშაობს. სტემერი ძებნის გასაუმჯობესებლად არსებობს: ამდენად, ის ტესტეთ.

დაწერეთ ფუნქცია სახელად run_functional_tests, რომელიც:

1. ძებნის სიმულაცია: დოკუმენტების სტრიქონების სიისა & საძიებო სიტყვის მიხედვით, სტემინგი გაუკეთეთ როგორც დოკუმენტებს, ისე მოთხოვნას, შემდეგ შეამოწმეთ, ჩნდება თუ არა სტემირებული მოთხოვნის ტერმინები სტემირებულ დოკუმენტებში. შეამოწმეთ, რომ 'running'-ის ძებნა პოულობს 'run' & 'runner'-ის შემცველ დოკუმენტს.

2. სიზუსტის შემოწმება: გადაამოწმეთ, რომ სტემინგი არ აჯგუფებს არასდადგენელ სიტყვებს. 'university' & 'universe' შეიძლება ერთ ფუძეს იზიარებდეს: შეამოწმეთ, ამუშავებს თუ არა ამას სტემერი (ნორმალურია, თუ ის ჯგუფავს; დოკუმენტირეთ ქცევა).

3. რეალური ტექსტის დამუშავება: სტემინგი გაუკეთეთ ინგლისური ტექსტის პარაგრაფის ყველა სიტყვას. გადაამოწმეთ, რომ გამომავალი გონივრულია: ცარიელი სტრიქონები, crash-ი არ არის, გამომავალს შეყვანის მსგავსი სიტყვების რაოდენობა აქვს.

def run_functional_tests():
    # Test 1: search finds related documents
    # Test 2: precision: check over-stemming
    # Test 3: real paragraph processing
    ...

რაც ააგეთ

რაც ააგეთ

დანერგეთ მოქმედი ინგლისური სტემერი:

- 12 სუფიქსის წესით (-tion, -ness, -ment, -able, -ible, -ies, -ied, -ier, -ing, -ed, -ly, -s)

- ორმაგი თანხმოვნის გასუფთავებით

- ჩუმი-e-ს აღდგენით

- Unit ტესტებით, ინტეგრაციული ტესტებით, & ფუნქციონალური ტესტებით

წარმომავლობა

სტემერი ემსახურება სამუშაოების გარდამტეხ ხაზს, რომელიც 1955 წელს ზელიგ ჰარისთან იწყება:

- ჰარისი (1955): აღმოაჩინა, რომ მორფემების საზღვრები სტატისტიკური სიგნალების სახით ვლინდება (მემკვიდრე მრავალფეროვნება)

- ლოვინსი (1968): პირველი გამოქვეყნებული სტემინგის ალგორითმი, 294 სუფიქსის წესი

- პორტერი (1980): გამარტივება ~60 წესამდე 5 ნაბიჯში, ათწლეულების განმავლობაში სტანდარტი გახდა

- Snowball (2001): პორტერის ჩარჩო გავრცელდა მრავალ ენაზე

- თქვენი სტემერი (დღეს): 12 წესი, იგივე ძირითადი პრინციპი

რაც შემდეგ შეგიძლიათ გააკეთოთ

- დანერგეთ სრული Porter ალგორითმი (კარგად არის დოკუმენტირებული & შესანიშნავი სავარჯიშოა)

- გადაიტანეთ სტემერი C-ზე 100-ჯერ სიჩქარის გასაუმჯობესებლად

- ააგეთ მარტივი საძიებო სისტემა, რომელიც სტემერს გამოიყენებს ტექსტური ფაილების ინდექსირებასა & მოთხოვნებისთვის

- შეადარეთ სტემერის გამომავალი NLTK-ის PorterStemmer-ს სიზუსტის გასაზომად

დღეს დაწერილი კოდი იგივე ფუნდამენტური ოპერაციაა, რომელიც მსოფლიოს ყოველ საძიებო სისტემაში მუშაობს. ცუდი არ არის ერთი დღის სამუშაოსთვის.