Հիմնավորում

Լեզվաբանական ձևաբանության մեջ, հիմնավորումը, սթեմինգը հոլովվող բառերի՝ իրենց արմատից շեղման նվազեցումն է, հիմքից կամ արմատից ընդհանուր առմամբ բառի սկզբնական ձևից շեղման նվազեցումը։ Պարտադիր չէ, որ բառի հիմքը լինի միակը և նման իր ձևաբանական արմատին. սովորաբար բավարար է, որ այդ բառերի ծառը (քարտեզը) կապված լինի մեկ արմատի հետ, նույնիսկ եթե այդ հիմքը իրականում այդ բառի ընդունելի՝ ճիշտ, արմատը չէ։ Հիմնավորման, սթեմինգի ալգորիթմները ուսումնասիրվել են համակարգչային գիտության մեջ 1968 թ-ից։ Շատ փնտրող համակարգեր նույն արմատով բառերը համարում են հոմանիշներ՝ որպես հարցման ընդհանրացում, օգտվողի հարցման ընդհանրացման համար, այսինքն պրոցես, որը կոչվում է միացում, համադրում, ընդհանրացում .

Սթեմինգի ծրագրերը ուղղակիորեն անրադառնում են սթեմինգի ալգորիթմներին կամ սթեմինգներին։

Օրինակներ

Անգլերենի համար հիմնավորողը (stemmer), օրինակ, կնույնացնի "կատուներ" string տեսակի բառը (և նաև հավանաբար "կատվանման", "կատվիկ" և այլն) որպես "կատու" արմատի վրա հիմնված բառեր, և "հիմնավորող"(stemmer), "հիմնավորում" (stemming), "հիմնավորոված"(stemmed) բառերը՝ հիմնված "հիմք" արմատի վրա։ Սթեմինգ ալգորիթմը կարճացնում է "ձկնորսություն", "ձուկ", "ձկնորս" բառերը ըստ արմատային բառի՝ "ձուկ":

Պատմություն

Առաջին երբևէ հրապարակված հիմնավորումը՝ (stemmer)-ը, գրվել է Ջուլի Բեթ Լովինսի կողմից 1968 թ.-ին։ Այս հրապարակումը հայտնի դարձավ իր առաջինը լինելու համար և մեծ ազդեցություն ունեցավ այս բնագավառոմ հետագա աշխատանքների համար։

Հաջորդ սթեմերը գրվեծ Մարթին Պորտերի կողմից և հրատարակվեց 1980 թ.-ին Program ամսագրի հուլիսի համարում։ Այս սթեմերը շատ լայնորեն օգտագործվեց և դարձավ դե-ֆակտո ստանդարտ ալգորիթմ, որն օգտագործվում էր անգլերենի սթեմինգի համար։ Դոկտոր Պորտերը ստացավ Tony Kent Strix մրցանակը 2000 թ.-ին իր՝ սթեմինգի և ինֆորացիայի վերականգնման վերաբերյալ աշխատության համար։

Պորտերի սթեմինգի շատ ալգորիթմների իրականացումներ գրվել են և անվճար տարածվել, այդ իրականացումներից շատերը պարունակում էին աննշան թերություններ։ Որպես արդյունք այս հիմքերը չունեցան իրենց պոտենցյալը։ Որպեսզի դուրս թողնել այդ սխալները, Մարթին պորտերը ստեղծեց ալգորիթմների պաշտոնական իրականացման անվճար ծրագրային ապահովում 2000 թ.-ի ընթացքում։ Նա երկարացրեց իր աշխատանքը մի քանի մյուս տարիների ընթացքում կառուցելով Snowball (ձնագնդիկ) ծրագրավորման լեզվուն, որը սթեմինգ ալգորիթմների գրելու համար նախատեսված հիմք է՝ կմախք, և իրականացրեց զարգացած անգլերեն սթեմերի(հիմնավորող) կառուցում մի շարք այլ լեզուների սթեմերների հետ միասին։

Ալգորիթմներ

Կան մի քանի տիպի սթեմինգի ալգորիթմներ, որոնք տարբերվում են ներկայացմամբ և ճշտությամբ և այն բանով, թե որքանով են սթեմինգի արգելքները հաղթահարված։

Brute-force ալգորիթմ

Brute force սթեմերները օգտագործում են փնտրում աղյուսակում սկզբունքը, որը պարունակում է արմատային և հոլովված ձևերի միջև փոխադարձ կապը։ Որպեսզի հիմնավորի(գտնի բառի հիմքը՝ արմատը) բառը, աղյուսակին հարցում է կատարվում գտնել համեմատվող հոլովումը։ Եթե համեմատվող հոլովումը գտնվում է, վերադարձվում է նման(ասոցոցված) արմատը։

Brute force-ի հարցումները քննադատվում են իրենց ընդհանուր հղկվածության, էլեգանտության պակասի համար, քանի որ ոչ մի ալգորիթմի դիմում չի կատարվում, որպեսզի ավելի մոտ լինենք խնդրի լուծմանը։ Այլ բառերով ասած, ավելի շատ օպերացիաներ են ներկայացված փնտրման ընթացքում, քան կարող էր անհրաժեշտ լինել։ Brute force փնտրումները օգտագործում են հսկայական տվյալներ, որպեսզի ներկայացվեն հարաբերությունների՝ կապերի ցանկը (կապված խնդրի հետ)։ Ալգորիթմը ճիշտ է միայն այն դեպքում, երբ հոլովված ձևը արդեն գոյություն ունի աղյուսակում։

Brute force ալգորիթմները հաղթահարում են այլ հարցումների կանչերը։ Տրված լեզվում ոչ բոլոր հոլովված բառերն են "հետևում կանոններին": Մինչ "running" բառը հեշտությամբ կհիմնավորովի(կգտնի իր արմատը՝ հիմքը) "run" բառով, այլընտրանքային՝ անկանոն բայերի դեպքում, "ran" բառը արդեն չի գտնի։ Վերջածանցի առանձնացման ալգորիթմները անկարող են այս խնդրի լուծումը իրականացնելու համար։ brute force ալգորիթմները միայն պահանջում են պահեստավորել եզակի հատուկ հարաբերության կապ "run"-ի և "ran"-ի միջև։

Brute force ալգորիթմները բավականին դժվար են ձևավորման համար, քանի որ տրված են հսկայական թվով հարաբերություններ, որոնք անհրաժեշտ է հավաքագրել հասանելի ճշտությունը ստանալու համար (այդ հարաբերությունների թիվը կարող է հասնել միլիոնների)։ Այնուամենայնիվ brute force ալգորիթմները հեշտ է զարգացնել, քանի որ սխալի դեպքում միայն անհրաժեշտ է համապատասխան տվյալը ավելացնել աղյուսակում։ Լեզվաբանության մեջ շատ քիչ իմացություն ունեցողները կարող են զարգացնել ալգորիթմը, այն դեպքում, երբ վերջածանցի առանձնացման ալգորիթմները պահանջում են որոշակի խորքային գիտելիքներ լեզվաբանության վերաբերյալ։

Տեխնիկական ճշգրտության համար, որոշ ծրագրեր կարող են օգտագործել վերջածանցի առանձնացում, փնտրման համար նախատեսված աղյուսակում, տրված տեքստի կառուցվածքը առաջացնելու համար, դրանից հետո միայն քննարկի փնտրման աղյուսակը սթեմինգի ժամանակ։ Սա չի պահանջվում որպես brute force-ի հարցում, այնուամենայնիվ փնտրման աղյուսակը ներառված է աշխատանքի մեջ։

Որպեսզի զարգացնել brute force-ի ալգորիթմը այն կարող է կառուցվել ըստ նախնական խոսքի մասի։ Ըստ այս պայմանի փնտրման աղյուսակը պարունամկում է նախածանցներ և վերջավորություններ, որոնք կապված են առանձնահատուկ խոսքի մասի հետ, ինչը էականորեն նվազեցնում է սթեմինգի չափազանցման սխալները։

Արտադրական մեթոդը

Որոշ ծրագրեր փորձում են ավտոմատ կերպով լրացնել արմատների և շեղումների համար նախատեսված աղյուսակը։ Արտադրական ալգորիթմը փորձում է ենթադրել տրված բառի հավանական շեղումները։ Օրինակ՝ եթե բառը "run" է, ապա ալգորիթմը ավտոմատ կկանչի "running" և "runs" ձևերը։ Սթեմինգի կոնցեպցիայի ավանդական իմաստով այս ալգորիթմը իր հակադարձ պրոցեսն է։ Բավական է փորձարկել կամ հեռացնել վերջածանցը, արտադրության ալգորիթմը կկանչի այդ վերջածանցները։ Այնուհետև brute force ալգորիթմը կարող է պարզապես հարցում կատարի բառերի միջև հարաբերությունների ավտոմատ կերպով կանչված աղյուսակը, որպեսզի գտնի տվյալ բառի արմատային ձևը։

Կան շատ տարբեր տիպի հայտնագործական, փորձնական մեթոդներ բառի շեղված լինելը հայտնաբերելու համար։ Որոշ ալգորիթմներ աշխատում են ֆոնետիկորեն՝ ուշադրություն դարձնելով բառի վերջin վանկերին։ Որոշները բավականին կոպիտ աշխատող են, որոնք օգտագործում են նորմալիզացման նման օրենքներ, ուսումնասիրելով միայն վերջին մի քանի բնութագրերը։ Մյուսները պարզապես օգտագործում են իմաստային բնութագիրը։

Այս մեթոդի առանձնացումը մյուս մետոցումներից այնքան էլ կարևոր չէ։ Այլ մոտեցումները կիսում են հիմնականում նույն տրամաբանությունը, բայց պարզապես աշխատում են հակառակ ուղղությամբ։ Որոշ սթեմինգի մոտեցումներ կարող են օգտագործել արտադրության մեթոդը շեղումների կանչման համար, և վերջածանցի առանձնացման ալգորիթմ՝ առանձնացնելով արմատային ձևը։

Այս մեթոդի մի թերությունն այն է, որ երաշխիք չկա, որ կոնկրետ շեղումը իրական է։ Օրինակ՝ այս մեթդը կարող է միացնել միմյանց "run" և "ly" բառերը՝ նոր բառ ստեղծելու համար, սակայն "runly" բառ գոյություն չունի։ "runly"-ն իրական բառ չէ։ Բացի այդ, դժվար թե երբևէ "runly" բառը օգտագործվի սթեմինգի ալգորիթմում, եթե այն չօգտագործվի իրականում։ Այսպիսով այս սխալը կարող է չազդել արդյունքի վրա, սական այն դուրս կլինի սթեմինգի ալգորիթմի ճշգրտությունից։ Այնուամենայնիվ նման սխալների շնորհիվ հարաբերությունների աղյուսակը բավականին հաճախ է օգտագործվում և մեծացնում է փնտրման աղյուսակում ամեն հավելյալ մուտքը մեծացնում է կոնկրետ բառի հետ առնչվող արմատի փնտրման համար պահանջվող ժամանակը։

Վերջածանցի առանձնացման ալգորիթմ

Վերջածանցի առանձնացման ալգորիթմը չի հենվում փնտրման աղյուսակի վրա, որը բաղկացած է շեղված ձևերի և արմատային ձևերի հարաբերություններից։ Փոխարենը տիպիկ կանոնների ավելի փոքր ցուցակ է պահվում, որը ապահովում է ալգորիթմի աշխատանքի համար անցկացման կարգը։ Տրված է լինում մուտքագրվող բառը, որպեսզի գտնվի այդ բառի արմատային ձևը։ Ահա ներառված կանոնների մի քանի օրինակներ.

• եթե բառը վերջանում է 'ed'-ով, հեռացնել 'ed'-ն
• եթե բառը վերջանում է 'ing'-ով, հեռացնել 'ing'-ը
• եթե բառը վերջանում է 'ly'-ով, հեռացնել 'ly'-ն

Վերջածանցի առանձնացման ալգորիթմը ավելի կիրառելի է շնորհիվ իր բավականին հեշտ մատուցման՝ համեմատած brute force ալգորիթմներին։ Ընդունելով այն մոտեցումը, որ լեզվաբանական և ձևաբանական առումով այն ավելի ճշգրիտ է մշակված՝ վերջածանցի առանձնացման ալգորիթմները երբեմն համարվում են որպես ոչ մշակված, քանի որ ներկայացված է աղքատիկ տվյալներով, և խնդիրների առաջ է կանգնում երբ գործ ենք ունենում բացառությունների հետ, օրինակ 'ran' և 'run' տարբերակը։ Այդ խնդրի լուծման համար այս ալգորիթմը առաջարկում է սահմանափակվել այն լեզվաբանական կատեգորիաներով , որոնք ունեն հայտնի վերջածանցներ և քիչ բացառություններ։ Սա, այնուամենայնիվ, պրոբլեմ է, քանի որ ոչ բոլոր խոսքի մասերն ունեն լավ ձևակերպված և բացառություններ չպարունակող կանոններ։

Հավելյալ ալգորիթմի չափանիշներ

Վերջածանցի առանձնացման ալգորիթմները կարող են տարբերվել արդյունքների զանազանությամբ։ Այդպիսի արդյունք է օրինակ, երբ ալգորիթմը պարտադրում է, որ արդյունքային բառը լինի իրական բառ տվյալ լեզվում։ Որոշ հարցումներ չեն պահանջում, որպեսզի բառը իրականում գոյություն ունենա լեզվի բառապաշարում ( լեզվում առկա բոլոր բառերի ամբողջությունը)։ Այլընտրանքորեն, որոշ վերջածանցների առանձնացում հարցում են կատարում մատուցել բոլոր հայտնի բառերի ձևաբանական արմատների բազա, որոնք գոյություն ունեն իրական բառերում։ Սա պահանջում է ստուգել ցուցակը բառերի առկայության համար՝ որոշում կայացնելու նպատակով։ Օրինակ, եթե տերմինը գոյություն չունի, կատարվում է այլընտրանքնային գործողությունը։ Այս այլընտրանքային գործողությունը կարող է ներառել մի քանի այլ չափանիշներ։ Պահանջվող բառի գոյություն չունենալը առաջ է քաշում վերջածանցների առանձնացման այլ տարբերակներ ընտրելու փորձեր։ Դա կարող է լինել մի դեպք, երբ օրինակ երկու կամ ավել վերջածանցներ առանձնացնելու կանոններ պիտի օգտագործվեն միևնույն ելքային տերմինի վրա, և որտեղ առաջանում է անորոշություն, թե որ կանոնը օգտագործվի։ Ալգորիթմը կարող է որոշել մի կանոնի առաջնայնությունը մյուսի հանդեպ։ Կամ ալգորիթմը կարող է մերժել մի կանոնը, որովհետև դա արդյունքներ է ներկայացնում տերմինի բացակայության դեպքում, մինչ մյուսը դա չի անում։ Օրինակ friendlies (ընկերասերներ) տերմինի դեպքում ալգորիթմը կարող է ies վերջածանցը առանձնացնի և ըստ համապատասխան կանոնի վերադարձնի friendl արդյունքը։ Այս բառը չենք գտնի բառապաշարի մեջ, որովհետև նման բառ գոյություն չունի անգլերենում, և հետևաբար այլ օրենքը կմերժվի։

Վերջածանցի առանձնացման հիմնական ալգորիթմի զարգացված տարբերակ է ածանի փոխարինման ալգորիթմը։ Վերջծանցի առանձնացման ալգորիթմին նման այս ալգորիթմը փոխարինում է վերջածանցը այլընտրանքային ածանցի հետ։ Օրինակ, կարող է լինել կանոն, որ ies փոխարինի y-ով։ Առաջին հայացքից թվում է, որ այս՝ friendlies օրինակում երկու ալգորիթմներն էլ նույն գործողությունն են կատարում, սակայն դա իրականում այդպես չէ։ Եթե վերջածանցի առանձնացման ալգորթմում մենք ստանում ենք friendl արդյունքը, որը իրական բառ չէ, ապա վերջածանցի փոխարինման ալգորիթմում մենք կստանանք friendly արդյունքը, ինչը իրական բառ է և նշանակում է ընկերասեր։ Ավելի խորանալով մանրուքների մեջ, պարզ մեթոդը կլինի կանոնների ցիկլիկ ձևերի օգտագործումը (ինչպես համակարգչի մասնագետներն են ասում՝ ռեկուրսիվորեն)։ Այս օրինակում ենթադրվում է գործողությունների հետևյալ հաջորդականությունը՝ առաջին քայլից հետո՝ ies վերջածանցի փոխարինումը y-ով, երկրորդ քայլը կլինի ly վերջածանցի առանձնացումը։ Այսինքն friendlies բառը դառնում է friendly` վերջածանցի փոխարինման ալգորիթմի միջոցով, և friend վերջածանցի առանձնացման ալգորիթմի միջացով։

Այս օրինակը թույլ է տալիս պատկերել տարբերությունը կանոնների վրա հիմնված հարցումի և brute force հարցումի միջև։ brute force հարցումի դեպքում, ալգորիթմը պետք է փնտրեր friendlies-ը հարյուրավոր և հազարավոր արմատից շեղված բառերի մեջ և լավագույն դեպքում գտներ friend արմատային բառը։ Կանոնների վրա հիմնված հարցումների դեպքում վերևը նշված կանոնները կօգտագործվեն և մենք կստանանք նույն արդյունքը։ Շանսերը մեծ են, որ կանոնների վրա հիմնված հարցումները ավելի արագ են արդյունք ստանում։

Առարկայական, թեմատիկ ալգորիթմ, լեմմատիզացիա

Ավելի բարդ մոտեցում է պահանջում այն դեպքը , երբ անհրաժեշտ է բառի արմատը գտնել ըստ նրա թեմայի` առարկայի, որը կոչվում է լեմմատիզացիա։ Այս պրոցեսը ներառում է առաջինը բառի՝ խոսքի մասի որոշումը և տարբեր նորմալիզացման կանոնների օգտագործումը ամեն խոսքի մասի համար։ Խոսքի մասի որոշումը առաջնային քայլ է արմատի փնտրման համար, քանի որ շատ լեզուների համար սթեմինգի օրենքները փոփոխվում են կախված բառի կոնկերետ որևէ խոսքի մաս լինելուց։

Այս մոտեցումը բարձր պայմանականություն ունի ճիշտ լեզվաբանական կատեգորիայի՝ խոսքի մասի ընտրության հարցում։ Մինչ կոնկրետ կատեգորիաների համար կանոնների նորմալիզացման հարցում որոշակի համընկնումներ կան, բառի սխալ կատեգորիայի ընտրության դեպքում կամ հնարավորություն չունենալով ճիշտ կատեգորիան ընտրել, զգալիորեն սահմանափակում է այս մոտեցման հավելյալ օգուտակարությունը՝ համեմատած վերջածանցի առանձնացման ալգորիթմի։ Հիմնական միտքը այն է, որ մենք հնարավորություն ունենք ավելի շատ ինֆորմացիա կորզել տվյալ բառի վերաբերյալ, քան կկարողանաինք օգտագործել կանոնների նորմալիզացման հնարավորությունը (որոնք հենց վերջածանցի առաձնացման կանոններն են).

Ստոխաստիկ` հավանականային ալգորիթմ

Ստոխաստիկ ալգորիթմներում ներառում են բառի արմատային մասի համնընկնման հավանականությունը։ Ստոխաստիկ ալգորիթմներին սովորեցվում է՝ "վարժեցվում" (նրանք "սովորում են") արմատային ձևիից շաղումները՝ հարաբերությունների աղյուսակի հիման վրա, որպեսզի զարգացնի հավանականային մոդելը։ Այս մոդելը արտահայտվում է լեզվաբանական բարդ կանոնների միջոցով, վերջածանցների առանձնացման և լեմմիատիզացիայի նման, բայց ավելի խորացված։ Սթեմինգը ներկայացվում է շեղված ձևի վարժեցված մոդելում մուտքագրվելով և ստողծելով արմատային ձևը, ըստ դրա ներքին կանոնների, ինչը կրկին նման է նշված մյուս երկու ալգորիթմներին, բացի ամենահամապատասխան կանոնը ներառելու որոշումից, կամ այն հարցից, թե արդյոք հիմնավորել բառը, թե վերադարձնել նույն արդյունքը, կամ օգտագործել հաճախականության տարբեր կանոններ, որոնք կիրառվում են այն դեպքում, երբ տվյալ բառը ունի ճիշտ լինելու ամենամեծ հավանականությունը։

Որոշ լեմմատիզացիայի ալգորիթմներ ստոխաստիկ են նրնանով, որ եթե տրված լինի մի բառ, որը կարող է պատկանել բաղադրյալ խոսքի մասերին, հավանականությունը կհամապատասխանի ամեն հավանական մասին։ Սա կարող է հաշվի առնել մոտակայքի բառերը, որը կոչվում է կոնտեքստ, կամ հաշվի չառնել։ Կոնտեքստից ազատված քերականությունները ընդհանրապես հաշվի չեն առնում որևէ հավելյալ ինֆորմացիա։ Ցանկացած դեպքում ամեն հավանական խոսքի մասի հավանականությունը որոշելուց հետո, ընտրվում է ամենահամապատասխան բառը, և օգտագործվում են նորմալիզացման կանոնները արմատային մասի որոշման համար։

n-gram վերլուծություն

Այստեղ gram տերմինը տեքստի չափման միավոր է, որը կարող է վերաբերել մեկ հատվածի, մեկ վանկի կամ մեկ բառի։ Թե սրանցից որն է օգտագործվում կախված է այն բանից, թե ով է ալգորիթմը մշակող ծրագրավորողը կամ հեղինակը։ n ածանցը համակարգչում օգտագործվող գիտական ժարգոն է, որը ներկայացնում է 'ցանկացած թիվ' կամ 'հասանելի թիվ' արտահայտությունները։ Կան հաճախակի օգտագործվող n-grams ենթաբազմություններ, ինչպես օրինակ բիգրամները, որոնք ներկայացնում են երկու գրամների հերթականություն (երկու հատվածներ կամ երկու բառեր, կամ երկու վանկեր մեկ տողում, որոնք անընդհատ օգտագործվում են տեքստում։ Տրիգրամները (երեք մասից բաղկացած) ևս բավականին հայտնի են։

Լեզվի մոդելավորման մեջ մենք կարող ենք գրել ծրագրային ապահովման ծրագիր, որը պահեստավորում է մեծ աղյուսակ բոլոր բառերի բիգրամների համար տեքստի մեծ մարմնում, որը կոչվում է կորպուս։ Ալգորիթմը կտպի բառը բառի ետևից, սլայդ պատուհանների նման, տեքստի սկզբից սկսած, և պահեստավորելով երկու բառերի հաջորդականությունները մինչև վերջին փաստաթղթի վերջին բառը։ Ելքային մասում ստեղծվում է բիգրամ աղյուսակ։ Աղյուսակում ամեն տող կոչվում է կորտեժ, որը պահպանում է առաջին բառը, հետո երկրորդը։ Տեքստերի մարմնի մեջ կարող է պահվել հավելյալ բնութագրիչ հատկություններ բիգրամի մասին, ինչպես օրինակ դրա հաճախականությունը (ամբողջ բիգրամի հայտնաբերման ընդհանուր հաճախականությունը) օգտագործված բոլոր աղյուսակներում։ Աղյուսակը ինքը կարող է պահեստավորել ինֆորմացիա ամեն եզակի բառի համար։ Օրինակ՝ "For example, this sentence contains bigrams" նախադասություը պարունակում է "for example" և "this sentence" բիգրամները։ Այսինքն կարելի է բիգրամը համարել բառակապակցություն՝ երկու բառից կազմված։

Աղյուսակի համար ալգորիթմը կարող է պահել առաջին բառին հաջորդող երկրորդ բառի հավանականությունը՝ գնահատելով ամեն բառի հաճախականությունը, և բիգրամներն ու այլ չափանիշների՝ օրինակ բիգրամների ամբողջ քանակը կամ այն բիգրամների քանակը, որտեղ առաջին բառը համընկնում է։ Աղյուսակի ալգորիթմը կարող է պահպանել երկրորդ բառի հավանականությունը, գնահատելով ամեն բառի հաճախականությունը և բիգրամների հաճախականությունը և նաև այլ չափանիշներ, ինչպես օրինակ բիգրամների ամբողջ թիվը կամ այն բիգրամների թիվը, որոնց մեջ առաջին բառը համընկնում է։

Բիգրամ հարաբերության մեջ առաջին բառը կարող է հասկացվել որպես այն կոնտեքստը, որը նկարագրում է երկրորդ բառը։ Այն որակավորում է երկրորդ բառը, մատուցելով հավելյալ ենթադրություն դրա նշանակության վերաբերյալ։ Մարդիկ բավականին հաճախ են օգտագործում կոնտեքստից բառի իմաստը հասկանալու մեթոդը։ Բառերը կարող են ունենալ բազմաթիվ նշանակություններ, ինչը կոչվում է իմաստ։ Բիգրամով մշակված կոնտեքստը մատուցում է այն ուղին ըստ որի կարող ենք որոշել օգտագործված բառի իմաստը ( իհարկե գրական աշխատություններում հաճախ բացառություններ են լինում)։ Ինչպես նշվել է, սթեմինգի ալգորիթմը կարող է օգտագործել կոնտեքստը որպես հավելյալ ինֆորմացիա, ինչը օգնում է ալգորիթմի կողմից մշակված ելքային բառի իմաստը որոշելու համար (օրինակ արդյոք տվյալ բառը հիմնավորոված է թե ոչ, կամ որ ալգորիթմն է ավելի համապատասխան օգտագործել՝ առանձնացման թե փոխարինման, կամ տվյալ բառը բայ է թե գոյական կամ այլ լեզվաբանական կատեգորիա, և այլն)։ Որովհետև ըստ հավանականությունների բառի որոշումը դա արդեն ստոխաստիկ ալգորիթմն է։

Ստոխաստիկ ալգորիթմների "թագավորության մեջ" մուտք գործելը կարող է զգալիորեն բարդացնել սթեմինգի ալգորիթմը, դարձնելով այն ավելի բարդ զարգացնելու, տարածման և պահպանման համար։ Եթե պարզ վերջածանցի առանձնացման ալգորիթմը մի քանի օրվա ծրագրավորումից հետո կարող է հասնել 80% ճգտության, ապա որքնան արժեքավոր կլինի n-gram սթեմերի աշխատանքը, որը հասնում է 90% ճշտության մի քանի ամիս աշխատանքի շնորհիվ։ Շատ խնդիրներ են առաջանում ստոխաստիկ սթեմերների հետ։ Ինչ կլինի եթե անհրաժեշտ կոնտեքստը, որը պիտի թարգմանվի, երբևէ չի օգտագործվել այդ փաստաթղթերում։ Ինչ կլինի, եթե ալգորիթմի բիգրամ աղյուսակը աղավաղվել է որևէ "վատ տեքստից" բառեր "սովորելով": brute force ալգորիթմի վերակոնֆիգուրացիան այնքան պարզ է, որքան վերցնել և հանել որևէ տող աղյուսակից։ Նման խափանումները և խնդիրները այժմ ուսումնասիրվում են համակարգչային գիտության մեջ։

Հիբրիտ մոտեցումներ

Հիբրիտ մոտեցումներ օգտագործում են երկու կամ ավելի մոտեցումներ վերը նշվածներից։ Պարզ օրինակ է վերջածանցների ծառի ալգոորիթմը, որը սկզբում հարցում է անում փնտրման աղյուսակից օգտագործելով brute force ալգորիթմը։ Այնուամենայնիվ, տրված լեզվում բառերի միջև մուտքագրված հարաբերությունների կապը փնտրելու փոխարեն փնտրման աղյուսակը ավելի քիչ ինֆորմացի ա է պահում, և օգտագործում է միայն շատ քիչ և հաճախ հանդիպող բացառություններ, ինչպես օրինակ "ran => run" տարբերակը։ Եթե բառը բացառության ցուցակում չէ, օգտագործում է վերջածանցների առանձնացման ալգորիթմը կամ լամմատիզացիան և ելք է ուղարկու արդյունքային բառը։

Ածանցի սթեմինգ

Լեզվագիտության մեջ, ածանց տերմինը վերաբերում է կամ նախածանցին կամ վերջածանցին։ Վերջածանցների հետ գործ ունենալուն ավելացված, որոշ հարցումներ վերաբերում են նաև մի քանի նախածանցների վերացմանը։ Օրինակ, եթե տրված լինի indefinitely բառը, "in" նախածանցը կարող է հառացվել։ Բոլոր վերը նշվածները կարելի համարել ածանցի առանձնացում։

Համապատասխանեցման ալգորիթմ

Նման ալգորիթմը օգտագործում է արմատների տվյալների բազան (օրինակ փաստափղփերի խումբ, որը պարունակում է արմատային բառեր)։ Այս արմատները, ինչպես նշվել է, պատահում է, որ օրինական՝ ճիշտ բառեր չլինեն։ Բառը հիմնավորելու նպատակով ալգորիթմը փորձում է համապատասխանեցնել այն տվյալների բազայի հիմքերի՝ արմատների հետ, օգտագործելով տարբեր հարկադրություններ (ինչպես օրինակ "be" կարճ նախածանցի դեպքում, որը հանդիսանում է "be", "been" և "being" բառերի հիմքը՝ արմատը, չհամարվի "beside" բառի արմատը)։

Լեզուների տարբերությունները

Բոլոր նախկինում կատարված գիտական շախատանքները այս ոլորտում անգլերենով են արված, այնուհետև այլ լեզուները ներգրավվել են այս ալգորիթմում

Հրեաերենը, հայերենը և արաբերենը մինչ այժմ համարվում են բավականին բարդ լեզուներ սթեմինգի համար։ Անգլերենում դա բավականին հեշտ է արվում ( դիտարկելով միայն մի քանի պատահական խնդիրներ ինչպես օրինակ "dries" բառը լինելով երրորդ դեմքի եզակի թվի բայաձևը առաջին և երկրորդ դեմքերում և հոգնակի թվում ունի "dry" ձևը, և նման շատ դեպքեր)։ Բայց սթեմերները բարդանում են երբ անհրաժեշտ է թարգմանություն կատարեկ որպես ձևաբանական, ուղղագրական և իմաստաբանական տեսանկյունից։ Օրինակ իտալերենի սթեմինգը շատ ավելի բարդ է քան անգլերենինը, որովհետև այն ավելի շատ է շեվում արմատային բառերից։ Ռուսերենը ավելի բարդ է, իր բավականին մեծ հոլովների պատճառով, և բացի այս ամենից օրինակ հւնգարերենը բավականին հեշտ է սթեմինգի համար՝ շնորհիվ իր՝ ճշգրիտ՝ առանց շեղումների կանոնների։

Բազմալեզու սթեմինգ

Բազմալեզու սէեմինգը օգտագործում է երկու կամ ավել լեզուների ձևաբանական կանոններ միաժամանակ, միայն մեկ լեզվի ձևաբանական կանոնների օգտագործման փոխարեն։

Սխալի մետրիկա

Սթեմինգի ալգորիթմում սխալների չափման համար կան երկու չափման միավորներ՝ վերահիմնավորում՝ overstemming և թերի հիմնավորում՝ understemming. Վերահիմնավորումը սխալ է, որտեղ երկու առանձին շեղված բառեր հիմնավորվում են նույն արմատին, բայց դա չպիտի այդպես լինի (սա կոչվում է սրական սխալ)։ Թերի հիմնավորումը այն սխալն է, երբ երկու առանձին շեղված արմատներ պիտի հիմնավորվեն մեկ արմատին, սակայն այդպես չի լինում, դա կոչվում է բացասական սխալ։ Սթեմինգի ալգորիթմը հակված է մինիմիզացնել ամեն տիպի սխալների հավանականությունը, չնայած մի տիպի սխալի հավանականության նվազեցումը կարող է մյուս տիպի սխալի հավանականությունը մեծացնի։

Գրականություն

• Dawson, J.L. (1974) Suffix Removal for Word Conflation, Bulletin of the Association for Literary and Linguistic Computing, 2(3)։ 33–46
• Frakes, W.B. (1984) Term Conflation for Information Retrieval, Cambridge University Press
• Frakes, W.B. & Fox, C.J. (2003) Strength and Similarity of Affix Removal Stemming Algorithms, SIGIR Forum, 37: 26–30
• Frakes, W. B. (1992) Stemming algorithms, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ
• Hafer, M.A. & Weiss, S.F., (1974) Word segmentation by letter successor varieties, Information Processing & Management 10 (11/12), 371–386.
• Harman, D., (1991) How effective is suffixing? Journal of the American Society for Information Science 42 (1), 7–15.
• Hull, D.A. (1996) Stemming Algorithms – A Case Study for Detailed Evaluation, JASIS, 47(1)։ 70–84
• Hull, D.A. & Grefenstette, G. (1996) A Detailed Analysis of English Stemming Algorithms, Xerox Technical Report
• Kraaij, W. & Pohlmann, R., 1996: Viewing stemming as recall enhancement, in H-P. Frei, D. Harman, P. Schauble & R. Wilkinson (eds.), Proceedings of the 17th ACM SIGIR conference held at Zurich, August 18–22, pp. 40–48.
• Krovetz, R. (1993) Viewing Morphology as an Inference Process, In Proceedings of ACM-SIGIR93, pp191–203
• Lennon, M., Pierce, D.S., Tarry, B.D. & Willett, P. (1981) An Evaluation of some Conflation Algorithms for Information Retrieval, Journal of Information Science, 3: 177–183
• Lovins, J. (1971) Error Evaluation for Stemming Algorithms as Clustering Algorithms, JASIS, 22: 28–40
• Lovins, J. B. "Development of a Stemming Algorithm." Mechanical Translation and Computational Linguistics 11, 1968, 22—31.
• Marie-Claire, J. and Smith, D. (2005) Conservative stemming for search and indexing
• Paice, C.D. (1990) Another Stemmer Արխիվացված 2011-07-22 Wayback Machine, SIGIR Forum, 24: 56–61
• Paice, C.D. (1996) Method for Evaluation of Stemming Algorithms based on Error Counting Արխիվացված 2012-12-09 archive.today, JASIS, 47(8)։ 632–649
• Popovic, M. and Willett, P., (1992) The effectiveness of stemmng for natural language access to Slovene textual data(չաշխատող հղում), Journal of the American Society for Information Science, 43(5), 384–390.
• Porter, M.F. (1980) An Algorithm for Suffix Stripping Արխիվացված 2007-05-28 Wayback Machine, Program, 14(3)։ 130–137
• Savoy, J., (1993) Stemming of French words based on grammatical categories Արխիվացված 2012-12-10 archive.today Journal of the American Society for Information Science, 44(1), 1–9.
• Ulmschneider, J.E. & Doszkocs, (1983) A practical stemming algorithm for online search assistance, Online Review, 7(4), 301–318.
• Xu, J. & Croft, W.B., (1998) Corpus-based stemming using coocurrence of word variants, ACM Transactions on Information Systems, 16(1), 61–81.

Արտաքին հղումներ

• Themis - open source IR framework, includes Porter stemmer implementation (PostgreSQL, Java API)
• Snowball - free stemming algorithms for many languages, includes source code, including stemmers for five romance languages
• Ruby-Stemmer Արխիվացված 2011-04-30 Wayback Machine - Ruby extension to Snowball API
• PECL - PHP extension to the Snowball API
• Oleander Porter's algorithm - stemming library in C++ released under BSD
• Unofficial home page of the Lovins stemming algorithm - with source code in a couple of languages
• Official home page of the Porter stemming algorithm - including source code in several languages
• Official home page of the Lancaster stemming algorithm Արխիվացված 2011-07-22 Wayback Machine - Lancaster University, UK
• Modifications to the Lancaster Stemming Algorithm - Extensions to improve the handling of errors in the rules, allow interactive testing, provide more precise stems, and add some flexibility for implementing finite state automata.
• Official home page of the UEA-Lite Stemmer Արխիվացված 2006-01-13 Wayback Machine - University of East Anglia, UK
• Overview of stemming algorithms Արխիվացված 2011-07-02 Wayback Machine
• PTStemmer - A Java/Python/.Net stemming toolkit for the Portuguese language
• jsSnowball Արխիվացված 2011-03-15 Wayback Machine - open source JavaScript implementation of Snowball stemming algorithms for many languages