Algo Visualizedდაიწყე სწავლა

რედაქტირების მანძილი

როცა ტელეფონი შეცდომით აკრეფილ სიტყვას ასწორებს, ან საძიებო სისტემა გეკითხება „ხომ არ გულისხმობდი…“, ის ითვლის, რამდენი ერთასოიანი ცვლილება აშორებს ორ სიტყვას. ეს რიცხვი რედაქტირების (ლევენშტეინის) მანძილია, უსქ-ის უახლოესი ნათესავი.

საშუალო⏱ 10 წთ

←ეყრდნობა

10უდიდესი საერთო ქვემიმდევრობარედაქტირების მანძილი იმავე ცხრილს ავსებს, რასაც უსქ, ჩასმით, წაშლითა და შეცვლით.

გზას უხსნის→

აქ გზამკვლევი სრულდება. გადახედე, რა გზა გაიარე.

1ისწავლე2ითამაშე3შეამოწმე4ივარჯიშე
01

ისწავლე

იდეა, მექანიზმი და ფასი.

01სამი ოპერაცია, ერთი რიცხვი

შეგვიძლია ასოს ჩასმა, ასოს წაშლა ან ერთი ასოს მეორით ჩანაცვლება, თითო 1-ის ფასად. A-დან B-მდე რედაქტირების მანძილი ოპერაციების უმცირესი რაოდენობაა, რომლითაც A B-ად იქცევა.

KITTEN → SITTING-ს 3 სჭირდება: K → S ჩანაცვლება, E → I ჩანაცვლება და ბოლოში G-ს ჩასმა. ნახაზზე ორი სიტყვა ერთმანეთის ქვეშაა განლაგებული: ერთმანეთზე დაწყობილი ტოლი ასოები უფასოა, განსხვავებული წყვილები ჩანაცვლებაა, ხოლო ცარიელი ადგილის პირისპირ მდგომი ასო ჩასმაა (ან წაშლა საპირისპირო მიმართულებით).

A-ს B-ად გადაქცევის ყოველი გზა ასეთი განლაგებაა, ამიტომ კითხვა ასე ჟღერს: რომელ განლაგებას აქვს ყველაზე ცოტა შეუსაბამობა და ცარიელი ადგილი? ყველას გადარჩევა ექსპონენციალურია. როგორც უსქ-ში, გზა პრეფიქსებზე კითხვის დასმაა.

KITTEN → SITTING: 3 ოპერაციაKITTEN–SITTINGჩანაცვლება ×2ჩასმა ×1- - უცვლელი

02რეკურენტული თანაფარდობა: სამი ისარი თითო უჯრაში

d[i][j] იყოს მანძილი A-ს პირველ i ასოსა და B-ს პირველ j ასოს შორის.

საბაზისო შემთხვევები: d[i][0] = i (ყველაფრის წაშლა) და d[0][j] = j (ყველაფრის ჩასმა).

დანარჩენისთვის შევადაროთ ბოლო ასოები A[i] და B[j]:

- თუ ტოლია, უფასოდ ვტოვებთ: d[i][j] = d[i−1][j−1]; - თუ არა, 1-ს ვიხდით სამი სვლიდან საუკეთესოსთვის: ჩანაცვლება (დიაგონალი) d[i−1][j−1], A[i]-ს წაშლა (ზემოდან) d[i−1][j], B[j]-ს ჩასმა (მარცხნიდან) d[i][j−1].

ანუ შეუსაბამობისას d[i][j] = 1 + min(დიაგონალი, ზედა, მარცხენა). შეადარე უსქ-ს: იგივე ცხრილი, იგივე სამი მეზობელი, მაგრამ სიგრძეების max-ის ნაცვლად ფასების min, და დიაგონალური სვლა ახლა განსხვავებული ასოების დროსაც დასაშვებია.

i−1, j−1i−1, ji, j−1i, jჩანაცვლება +1(ტოლ ასოებზე +0)წაშლა +1ჩასმა +1d[i][j] = min(სამი ისარი)

03შევსება, უკან სვლა და გამოყენება

(m+1) × (n+1) ცხრილს სტრიქონ-სტრიქონ ვავსებთ; ქვედა მარჯვენა უჯრა პასუხია. KITTEN → SITTING-ისთვის ის 3-ია.

ოპერაციების ჩამოსაწერად კუთხიდან უკან მივდივართ ზუსტად ისე, როგორც უსქ-ში: დიაგონალური ნაბიჯი ტოლი ასოებით „დატოვებაა“, დიაგონალური ნაბიჯი განსხვავებულით „ჩანაცვლება“, ნაბიჯი ზემოთ „წაშლა“, ნაბიჯი მარცხნივ „ჩასმა“. ვაგროვებთ და ვაბრუნებთ.

სირთულე: O(m·n) დრო; მხოლოდ მანძილისთვის ორი სტრიქონი O(n) მეხსიერებას იძლევა.

ვარიაციები წონების ან სვლების შეცვლით მიიღება: მხოლოდ ჩასმა და წაშლა იძლევა m + n − 2·უსქ-ს (ანუ მას უსქ ხსნის); მეზობელი ასოების გადასმის დაშვება დამერაუს მანძილს იძლევა; ჩანაცვლებისთვის სხვა ფასის მინიჭება კი ბიოლოგიაში გამოყენებულ მიმდევრობების შედარების ქულებს. ცხრილი და უკან სვლა არასდროს იცვლება.

d[i][j] = მანძილი A-ს i ასოსა და B-ს j ასოს შორისεSITTINGεKITTEN01234567112345672212345633212345443212345543223466543323ოპერაციები:K → SI, T, T უცვლელიE → IN უცვლელი+ Gd[6][7] = 3

ფასი ერთი შეხედვით

ცხრილის შევსებაO(m·n)
მხოლოდ მანძილი, ორი სტრიქონიO(n) memory
ოპერაციების აღდგენაO(m + n)

დაიმახსოვრე

  1. d[i][j] პრეფიქსებს შორის მანძილია; საზღვარზე i ან j წერია, რადგან ცარიელ პრეფიქსს ამდენი ჩასმა ან წაშლა სჭირდება.
  2. ტოლი ასოები დიაგონალს იმეორებს; სხვა შემთხვევაში 1 + min დიაგონალიდან (ჩანაცვლება), ზედადან (წაშლა) და მარცხენადან (ჩასმა).
  3. ეს უსქ-ის იგივე ცხრილის ჩონჩხია, სიგრძეებისა და max-ის ნაცვლად ფასებითა და min-ით.
02

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: ყოველი შეუსაბამო უჯრა სამ კანდიდატს აჩვენებს (ჩანაცვლება, წაშლა, ჩასმა). შევსების შემდეგ უკან სვლა ოპერაციებს რიგით ჩამოწერს. სცადე HORSE → ROS.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →
✎ შენი მონაცემებიორი სიტყვა, თითო 9 ასომდე, მაგ. HORSE → ROS.

რედაქტირების მანძილი: KITTEN → SITTING

εSITTING
ε01234567
K1·······
I2·······
T3·······
T4·······
E5·······
N6·······

ოპერაციები

∅
რედაქტირების მანძილი: ჩასმის/წაშლის/ჩანაცვლების ოპერაციების უმცირესი რაოდენობა, რომლითაც KITTEN გადაიქცევა SITTING-ად. სტრიქონი 0 = ყველაფრის ჩასმა; სვეტი 0 = ყველაფრის წაშლა.

ფსევდოკოდი

 1 d[i][0]=i (delete all), d[0][j]=j (insert all) 2 if A[i]==B[j]: d[i][j] = d[i-1][j-1]        // keep 3 else: d[i][j] = 1 + min(diag=substitute, up=delete, left=insert) 4 reconstruct: follow the arrows back, listing operations
1 / 1
03

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

რას უდრის რედაქტირების მანძილი HORSE-დან ROS-მდე?

№2

ცხრილში (i, j)-დან (i−1, j)-ზე დაბრუნება რომელ ოპერაციას ნიშნავს?

№3

რას უდრის d[0][5]?

04

ივარჯიშე

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

LeetCodeEdit Distance საშუალო↗CSESEdit Distance საშუალო↗LeetCodeMinimum ASCII Delete Sum for Two Strings საშუალო↗LeetCodeDistinct Subsequences მოწინავე↗