I nte rna t io na l J o urna l o f   I nfo rm a t ics a nd   Co m m un ica t io n T ec hn o lo g y   ( I J - I CT )   Vo l.  15 ,   No .   3 Sep tem b er   20 26 ,   p p .   1 3 4 0 ~ 1 3 5 1   I SS N:  2252 - 8 7 7 6 DOI 1 0 . 1 1 5 9 1 /iji ct . v15 i 3 . pp 1 3 4 0 - 1 3 5 1          1340       J o ur na l ho m ep a g e h ttp : //ij ict. ia esco r e. co m   Ev a lua tion o text  correction  using   a  com bina tion o Lev enshtein d ista nce   a nd  Tri e   a lg o rithm       Cy nthia   Na t a lie Abba   Su g a nd a   G irsa ng   D e p a r t me n t   o f   C o mp u t e r   S c i e n c e ,   B I N U S   G r a d u a t e   P r o g r a m   M a st e r   o f   C o mp u t e r   S c i e n c e ,     B i n a   N u sa n t a r a   U n i v e r si t y ,   W e s t   Ja k a r t a ,   I n d o n e s i a       Art icle  I nfo     AB S T RAC T   A r ticle  his to r y:   R ec eiv ed   J u l 1 0 ,   2 0 2 4   R ev is ed   J u n   2 4 ,   2 0 2 6   Acc ep ted   J u l 5 ,   2 0 2 6       No wa d a y s,  tec h n o l o g y   is   a d v a n c in g   with   v a ri o u a p p li c a ti o n s,   e sp e c ially   i n   tex p ro c e ss in g ,   su c h   a n e w re c o m m e n d a ti o n s,  se n ti m e n t   a n a ly sis,  a u to m a ti c   sc o rin g ,   a n d   lan g u a g e   tran sla ti o n .   In   so m e   c a se s,  sp e ll in g   e rro rs   o ften   o c c u wh e n   in p u t ti n g   tex f o th e   tran sla ti o n   p r o c e ss ,   n e c e ss it a ti n g   tex c o rre c ti o n   m e th o d s   to   d isp lay   s u g g e stio n a a   re su lt .   Th e re fo re ,   th e   p ro b lem   sta tem e n ra ise d   is  a b o u h o t o   i m p ro v e   t h e   a c c u ra c y   o tex c o rre c ti o n   a n d   e v a lu a te  th e   tran sla ti o n   q u a li t y   a th e   wo rd   lev e a fter  c o rre c ti n g   in p u te x i n   th e   c o n tex o tran sla ti o n   fro m   I n d o n e sia n   to   En g li sh .   T h is  re se a rc h   a ims   to   d e v e lo p   a n d   e v a l u a te  th e   c o m b i n a ti o n   o Lev e n sh tein   d istan c e   a lg o rit h m   a n d   Tri e   to   c o rre c in p u te x a n d   e v a lu a te  th e   tran sla ti o n   q u a li t y   a t   th e   wo rd   lev e l   a fter  c o rre c ti n g   tex t.   T h e re   a re   v a rio u tex c o rre c ti o n   m e th o d s,  su c h   a Ha m m in g   d istan c e ,   Lev e n sh tei n   d istan c e ,   Da m e ra u - Lev e n sh tein   d istan c e a n d   N - G ra m .   A m o n g   se v e ra tex c o rre c ti o n   m e th o d s.  Lev e n sh tei n   d istan c e   a lg o rit h m   is  c o m m o n l y   u se d   to   c a lcu late   th e   d istan c e   b e twe e n   tex ts  a n d   c a n   b e   e n h a n c e d   b y   u sin g   a   Tr ie   fo r   m o re   e fficie n c o m p u tati o n   i n   e v a lu a ti n g   tex c o rre c ti o n .   T h is  re se a rc h   m e t h o d   re su lt e d   i n   a n   a c c u ra c y   o f   8 2 . 2 5 %   wit h   a n   F 1   sc o re   o 8 4 . 3 9 % ,   wh e re   th e   d e v e lo p e d   tex t   c o rre c ti o n   m o d e p ro d u c e d   a   g o o d   tra n sla ti o n   u si n g   BLE sc o re   with   a n   in c re a se   o 1 . 5 5 %   a fter  tex t   c o rre c ti o n .   K ey w o r d s :   C h atGPT   Go o g le  tr an s late   L ev en s h tein   d is tan ce   T ex t c o r r ec tio n   T r ie   alg o r ith m   T h is i a n   o p e n   a c c e ss   a rticle   u n d e r th e   CC B Y - SA   li c e n se .     C o r r e s p o nd ing   A uth o r :   Ab b Su g an d Gir s an g   Dep ar tm en t o f   C o m p u ter   Scie n ce ,   B I NUS  Gr ad u ate  Pro g r a m   Ma s ter   o f   C o m p u te r   Scien c e   B in Nu s an tar Un iv er s ity   Stre et  K.   H.   Sy ah d an   9 ,   Kem a n g g is an ,   Palm er ah ,   W est J ak ar ta ,   I n d o n esia   E m ail:  ag ir s an g @ b in u s . ed u       1.   I NT RO D UCT I O N   Fo r eig n   lan g u ag tr an s latio n   i s   th in ter p r etatio n   o f   tex f r o m   th n ativ lan g u a g e,   r esu ltin g   in   tex th at  co n v e y s   s im ilar   m ess ag e   [ 1 ] .   W ith   th ad v a n ce m en o f   tech n o lo g y ,   f o r eig n   la n g u ag tr an s latio n   ca n   n o b lear n e d   an d   p er f o r m ed   u s in g   ap p licatio n s ,   o n o f   wh ich   is   Go o g le  T r an s late   [ 2 ] .   I n   s o m ca s es,  s p e l li n g   e r r o r s   o f te n   o c c u r   w h e n   i n p u t t i n g   t e x t   f o r   t h e   t r a n s l at i o n   p r o c e s s ,   n e c ess i t at i n g   te x c o r r e c t i o n   m et h o d s   t o   d i s p l a y   s u g g e s ti o n s   as   a   r e s u l t   o f   i n p u t   t e x t   c o r r e ct i o n   t o   h e lp   u s e r s   o b t a i n   o p ti m a l   t r a n s l at io n   r e s u l t s .   Var io u s   m eth o d s   h av e   b ee n   p r o p o s ed   to   h an d le  tex c o r r e ctio n   p r o b lem s   [ 3 ] - [ 5 ] ,   s u ch   as  N - Gr am   an d   L e v en s h tein   d is tan ce   [ 6 ] ,   wh ich   ca n   p r o v id e   g o o d   r esu lts ,   b u t   th ese   m eth o d s   o f ten   d is p lay   to o   m an y   s u g g esti o n s .   Me an wh ile,   th e   r esear ch   o n   L ev en s h tein   d i s tan ce   an d   C o s in Similar ity   h as  n o p r o v id e d   ap p r o p r iate  s u g g esti o n s   d u t o   th lack   o f   w o r d   g r o u p in g .   E d it  Dis tan ce   an d   B E R T - b ased   m ask   lan g u ag e   m o d el   m eth o d s   also   n ee d   to   b d ev elo p e d   f o r   te x co r r ec ti o n   b ased   o n   e x is tin g   co n tex ts   [ 7 ] .   T h er e f o r e,   th e   p r o b lem   s tatem en r aised   is   ab o u h o to   im p r o v e   th e   ac cu r a cy   o f   tex t   co r r ec tio n   an d   ev al u ate  th tr a n s latio n   q u ality   at  th wo r d   lev el  af te r   co r r ec tin g   i n p u t te x t i n   th co n tex t o f   tr a n s latio n   f r o m   I n d o n esian   to   E n g lis h .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J I n f   &   C o m m u n   T ec h n o l     I SS N:   2252 - 8 7 7 6       E va lu a tio n   o f te xt  co r r ec tio n   u s in g   a   co mb in a tio n   o L ev en s h tein   d is ta n ce   a n d   Tr ie   … ( C yn th ia   N a ta lie )   1341   Pre v io u s   r esear ch   co n d u cted   b y   Yo u n ess   C h aa b an d   h is   co ll ea g u es,  ap p l y in g   Dam er au - L e v en s h tein   alg o r ith m   an d   N - g r am   h as  h a n d led   s p ellin g   er r o r s   in   Am az ig h   lan g u a g e,   h o wev er ,   th is   c o m b in atio n   c o r r ec ts   o n ly   s p ellin g   e r r o r s   [ 6 ] .   I n   c o n tr ast,  Vin y   C h r is tan ti  an d   h er   team ' s   s tu d y   s u cc ess f u lly   h an d le d   s p ellin g   er r o r s   u s in g   T r ie   an d   Dam er au - L ev en s h tein   d is tan ce   B ig r am .   Ho wev er ,   th is   ap p r o ac h   r eq u ir es  s u b s tan tial  m em o r y   u s ag f o r   wo r d   co r r ec tio n   [ 8 ] .   Mo r e o v er ,   R o m ila  Aziz   an d   team   h as  im p lem en ted     Dam er au - L ev e n s h tein   d is tan c e   T r ig r am   in   c o r r ec tin g   co n te x er r o r s ,   s till   th is   r esear ch   ca n   b en h a n ce d   to   d etec an d   co r r ec m u ltip le  co n te x tu al   er r o r s   in   s in g l s en ten ce   [ 9 ] .   Oth er   r esea r ch   r elate d   to   th e   co m b in atio n   o f   L ev e n s h tein   d is tan ce   an d   R ab in - Kar p   alg o r ith m s   co n d u cted   b y   An d r Hasu d u n g an   L u b is   an d   team ,   s u cc ee d ed   in   s h o win g   th at  th c o m b in ati o n   o f   th t wo   alg o r ith m s   p er f o r m s   g o o d   a cc u r ac y   an d   its   ap p licatio n   ca n   b e   im p r o v e d   b ased   o n   ce r tain   p ar am et er s ,   s u ch   as  N - Gr a m ,   B ase  an d   Mo d u lo   [ 1 0 ]   Similar ly ,   Aaq ila  Dh iy aa n is af Go en awa n   ap p lied   T r ie   an d   d ep th - f ir s s ea r c h   alg o r ith m s   t o   im p lem e n s ea r ch   s u g g esti o n s ,   y et  th is   r esear ch ' s   lim i tatio n   lies   in   its   in ab ilit y   to   d is p lay   f r eq u en tly   u s er - in p u tted   wo r d   r ec o m m en d atio n s   [ 1 1 ] .   An o t h er   s tu d y   b y   Kav ita  T .   Patil  an d   co lleag u es  co r r ec te d   Ma r ath wo r d s   u s in g   co m b in atio n s   o f   L ev e n s h tein   d is tan ce   an d   C o s in Similar it y .   Ho wev er ,   wo r d   s u g g esti o n s   in   Ma r ath d id   n o t   y ield   p r ec is r esu lts   d u to   u n g r o u p ed   wo r d s   in   th v o ca b u lar y   s et   [ 1 2 ]   B ased   o n   p r e v io u s   r esear ch ,   s ev er al  is s u es  s u ch   as  ex ce s s iv an d   u n g r o u p ed   wo r d   co r r ec tio n   r esu lts ,   im p r ec is wo r d   s u g g esti o n s ,   an d   h ig h   m em o r y   u s ag r eq u ir f u r t h er   ev al u atio n .   E n h a n cin g   L ev en s h tein   d is tan ce   an d   T r ie   alg o r ith m   c o u ld   lead   to   m o r ef f icien te x co r r ec tio n   ev alu atio n s   [ 1 3 ] T r ie   d ata  s tr u ctu r es   ca n   b s to r ed   f o r   tex p r o ce s s in g ,   r ed u cin g   m em o r y   u s a g in   g r o u p in g   tex ts   b ased   o n   s im ilar   p r ef ix es,  co m b in ed   with   L ev en s h tein   d is tan ce   alg o r ith m   to   ca lcu la te  th d is tan ce   b etwe en   tex ts .   T h is   c o m b in atio n   o f f er s   an   ex ce llen b alan ce   b e twee n   s p ee d   an d   ac cu r ac y .   T h ap p licatio n   o f   T r ie   allo ws  f o r   f ast  an d   ef f icien t   s im ilar   p r ef ix   s ea r ch es   [ 1 4 ] ,   wh i le  L ev en s h tein   d is tan ce   alg o r ith m   p r o v id es  h ig h   ac cu r a cy   in   d etec tin g   an d   co r r ec tin g   s p ellin g   er r o r s   an d   is   n o af f ec ted   b y   th e   len g th   o f   th e   tex t.   T h e   co n tr i b u tio n s   o f   o u r   w o r k   in clu d e   th f o llo win g   item s :   -   I n tr o d u ce   th c o m b in atio n   o f   L ev en s h tein   d is tan ce   an d   T r ie   alg o r ith m   f o r   tex t c o r r ec tio n   p u r p o s e.   -   E v alu ate  th e   co m b in atio n   o f   L ev e n s h tein   d is tan ce   an d   T r ie   alg o r ith m   u s in g   C o n f u s io n   Ma tr ix ,     AUC - R O C   C u r v an d   B L E Sco r m ea s u r em en t.   T h is   p ap er   is   s tr u ctu r ed   as  f o l lo ws:   1 .   I n tr o d u ctio n ,   2 .   T h Pro p o s e d   Me th o d   3 .   Me th o d ,   4 .   R esu lt s   an d   Dis cu s s io n ,   an d   5 .   C o n cl u s io n .   Sectio n   1   i n tr o d u ce s   th p r o p o s ed   ap p r o ac h .   Sectio n   2   d escr ib es  r elate d   wo r k   d o n i n   th is   ar ea .   Sectio n   3   d escr ib es  r esear ch   m eth o d .   Sectio n   4   d escr ib es  th e   r es u lts   o f   th p r o p o s ed   ap p r o ac h   f o llo we d   b y   d is cu s s io n ,   an d   s ec tio n   5   c o n clu d es th p ap er .       2.   T H E   P RO P O SE M E T H O D   Var io u s   r esear ch es  h av b ee n   co n d u cted   in   th co n tex o f   tex co r r ec tio n   u s in g   co m b in at io n s   o f   th L ev en s h tein   d is tan ce   Alg o r ith m .   R esear ch   o n   th co m b i n atio n   o f   Dam er au   L e v en s h tein   d is tan ce   an d     N - Gr am   was  co n d u cted   b y   Y o u n ess   C h aa b a n d   h is   co llea g u es  [ 6 ]   to   id en tif y   s p ellin g   er r o r s   in   Am az ig h   co r p u s   lan g u ag e.   T h N - Gr a m   m eth o d   was  u s ed   to   m ea s u r e d   f o r   r an d o m   s p ellin g   er r o r s   f r o m   th d ictio n ar y .   T h r esu lts   s h o wed   th ac h ie v ed   F - m ea s u r v alu e   r an g ed   f r o m   8 6 . 6 2 % to   9 8 . 7 4 % .   Oth er   r esear ch   o n   th co m b in atio n   o f   ed it d is tan ce   alg o r ith m s   was  co n d u cted   b y   Vin y   C h r is tan ti  an d   team   [ 8 ]   b y   co m b i n in g   Da m er au - L ev e n s h tein   d is tan ce   with   T r ie   in   th co n tex o f   s p ell  ch ec k in g .     T h s tu d y   s h o we d   wo r d   co r r ec tio n   ac cu r ac y   o f   8 4 . 6 2 a n d   s en ten ce   c o r r ec tio n   ac cu r ac y   o f   5 0 %,  with   a   p r o ce s s in g   tim p er   s en ten ce   o f   1 8 . 8 9   m s .   Fu r th er m o r e,   t h r esear ch   o n   th co m b i n atio n   o f   L ev en s h tein   d is tan ce   an d   R ab in - Kar p   alg o r ith m s   was  co n d u cted   b y   An d r Hasu d u n g an   L u b is   a n d   team   [ 1 0 ]   t o   im p r o v e   th ac cu r ac y   o f   d o c u m en s im ilar ity .   T h R ab in - Kar p   alg o r i th m   is   s ea r ch   alg o r ith m   th at   lo o k s   f o r   s u b s tr in g   p atter n s   in   tex u s in g   h ash in g ,   ty p ically   u s ed   to   m atch   tex with   v ar io u s   p atter n s .   I n   th is   s tu d y ,   L ev en s h tein   d is tan ce   r ep lace d   th h ash   ca l cu latio n   in   th R ab in - Kar p   al g o r ith m   b y   ca lcu latin g   th n u m b er   o f   h ash es  with   th s am v alu in   b o th   d o c u m en ts .   B y   ad d in g   th L ev en s h tein   d is tan ce   alg o r ith m ,   th d is tan ce   ca lcu latio n   b etwe en   th two   d o cu m en ts   r esu lted   in   b etter   ac cu r ac y .   T h s tu d y   s h o wed   th at  th co m b in atio n   o f   th ese  two   alg o r ith m s   p r o d u c ed   b etter   ac cu r ac y ,   wh ich   co u ld   b f u r th e r   im p r o v e d   b ased   o n   ce r tain   p ar am eter s ,   s u ch   as  N - Gr am ,   B ase,   an d   Mo d u lo .   An o th er   r esear ch   c o m b in i n g   en h an ce d   N - g r am   a n d   L e v en s h tein   d is tan ce   alg o r ith m   c o n d u cted   b y   Salah   Al - Hag r ee   a n d   h is   tea m   s h o wed   s im ilar ity   m ea n   o f   0 . 9 0   an d   F - m ea s u r e   m ea n   o f   0 . 9 1   in   n am e   m atch in g   [ 1 5 ] .   A   s im ilar   s tu d y   o n   th e   au to c o m p lete  te x f e atu r in   an   I n d o n esian   d ictio n ar y   c o n d u cted   b y   Go en awa n   an d   team   [ 1 1 ]   w as  also   im p lem en ted   with   t h T r ie   a n d   d ep th - f ir s s ea r ch   alg o r ith m .   T h is   co m b in ati o n   a p p lied   to   s h o r te n   th u s er ' s   ty p in g   tim e,   wh er e   th is   f ea tu r wo u ld   d is p lay   lis t o f   wo r d s   th at  th e   u s er   m ig h m ea n   with o u h a v in g   to   ty p e   th wo r d   c o m p l etely .   T h r esu lts   in clu d ed   i m p lem en tin g   s ea r ch   s u g g esti o n s   b ased   o n   n o d e   lo c atio n   in   th test in g .     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8 7 7 6   I n t J I n f   &   C o m m u n   T ec h n o l ,   Vo l.  15 ,   No .   3 Sep tem b er   20 26 1 3 4 0 - 1 3 5 1   1342   Similar   s tu d y   was  c o n d u cted   o n   lan g u ag e   m o d els  ( L Ms)   b y   ap p ly in g   a   s im ilar   alg o r it h m ,   b y te  p ai r   en co d in g   ( B PE) ,   to   ev alu ate  t h m o d el  b y   co m p ar in g   th i m p lem en tatio n   o f   B PE  to k e n i za tio n   an d   Un ig r am   LM   to k en izatio n   [ 1 6 ] .   T h e x p er im en tal  r esu lts   s h o wed   t h a th a d ju s tm en m o d el   tr ain e d   with   U n ig r am   LM   to k en izatio n   p er f o r m ed   b etter   th an   t h ad j u s tm en m o d el  tr ain ed   with   B PE  to k e n izatio n .   T h is   s tu d y   s h o wed   th at  alth o u g h   th e   B PE  alg o r it h m   was  q u ite   u s ef u in   tr an s la tin g   OOV  wo r d s   i n   th e   d ataset,   m o s OOV  wo r d s   wer s till   in co r r ec tly   tr an s lated   [1 7 ] .   R esear ch   co m b in in g   th e   E d it   Dis tan ce   alg o r ith m   was  a g ain   co n d u cte d   b y   Fatem eh   T o h id i an   [ 7 ]   with   B E R T - b ased   m ask ed   lan g u ag m o d e f o r   s p ell  co r r ec t io n .   B E R T   is   tr an s f o r m e r - b ased   ar ch itectu r e   in itially   tr ain ed   o n   m ask e d   l an g u ag e   m o d el  to   f in d   m is s p e lled   wo r d   ca n d id ates  an d   s elec th b est  ca n d id ate   b ased   o n   E d it  Dis tan ce   ca lcu latio n s .   T h s tu d y   s h o wed   th at   th co m b in atio n   o f   m ask ed   lan g u ag m o d el  an d   E d it  Dis tan ce   r esu lted   in   r ec all  o f   8 1 . 2 1 in   s p ell  co r r ec tio n   o b tain e d   f r o m   p r ed i ctio n   r an k in g   an d   co m b in in g   ch ar ac ter - lev el  cr iter ia  ( ed it  d is tan ce )   with   B E R T   p r ed ictio n   s co r es.  I n   th s am y ea r ,     co m p ar ativ s tu d y   was  co n d u cted   co m p a r in g   th u s o f   t h m in im u m   ed it  d is tan ce   alg o r ith m   with   C o s in e   Similar ity   to   c h ec k   an d   co r r e ct  s p ellin g   er r o r s   in   Ma r ath i.  T h m in im u m   e d it  d is tan ce   i s   ch ar ac ter - b ased   ap p r o ac h ,   wh ile   C o s in s im ilar ity   is   s im ilar ity   a p p r o ac h   b ased   o n   ce r tain   te r m s .   T h e   s tu d y   s h o we d   th e   b est  ac cu r ac y   o f   8 5 . 8 8 % a n d   8 6 . 7 6 % with   th u s o f   m in im u m   e d it d is tan ce   an d   C o s in s im ilar ity   [ 1 2 ] .     T h latest  r esear ch   o n   th L e v en s h tein   d is tan ce   alg o r ith m   co m b in ed   with   s ev er al  s tr in g   m atch in g   alg o r ith m s ,   s u ch   as  th e   Gestalt  an d   SweetCo at - 2 alg o r ith m s ,   was  co n d u cted   to   f in d   c o m p ar is o n   p atter n s   o f   th two   s tr in g s   i n   th e   B an g la   lan g u a g e.   T h Gestalt  alg o r it h m   d eter m in es  tex d ata  p atte r n s   u s in g   m ac h in e   lear n in g   an d   ca n   p r ed ict  te x b ased   o n   th ese  p atter n s   u s in g   th SweetCo at - 2 m o d el.   SweetCo at - 2 is   b u ilt  o n   a   two - d im e n s io n al  m o d el,   wh er e   th p o s itio n   o f   a   p o in ca n   b d eter m in ed   u s in g   x   an d   y - ax is   v al u es.    T h r esu lts   o f   th is   s tu d y   s h o wed   th at  th e   a p p licatio n   o f   s p ellin g   s u g g esti o n s   was  s u cc ess f u lly   im p r o v ed   b y   9 2 . 4 0 4 %,  with   ac c u r ac y   ca lc u lated   b ased   o n   co r r ec t   s p el lin g   s u g g esti o n s   in   th e   B an g la  lan g u a g e   [ 1 8 ] .   Her ea f ter   in   th e   s am y ea r ,   th r esear ch   u s in g   au g m e n ted   Dam er au - L ev en s h tein   d i s tan ce   s u c ce s s f u lly   d ev elo p e d   b y   N u r zh a n   Mu k az h an o v   a n d   team ,   r esu lted   b est  ac cu r ac y   o f   9 2 . 8 in   Kaz ak h   tex t   [ 1 9 ] .   Su m m ar y   o f   th liter atu r e   r ev i ew  f o r   co m b in atio n   o f   L e v en s h tein   d is tan ce   an d   T r ie   p r esen t ed   in   T ab le  1 .       T ab le  1 .   R elate d   wo r k   o f   c o m b in atio n   o f   L ev e n s h tein   d is tan ce   an d   T r ie   al g o r ith m   Y e a r   M e t h o d s   La n g u a g e   D a t a s e t   R e s u l t   2 0 1 8   [ 8 ]   Tr i e   a n d   d a mera u - Le v e n s h t e i n   d i st a n c e   b i g r a m   I n d o n e si a n   K o mp a s New s   A c c u r a c y   8 4 . 6 2   Ti me   1 8 . 8 9   ms   2 0 1 8   [ 1 0 ]   Le v e n s h t e i n   d i st a n c e   a n d   r a b i n   k a r p   En g l i sh   D o c u me n t s   1 0 o f   d o c u m e n t   s i mi l a r i t y   2 0 1 9   [ 1 5 ]   N - g r a a n d   L e v e n sh t e i n   d i s t a n c e   En g l i sh ,   P o r t u g e se,   a n d   A r a b i c   En g l i sh ,   P o r t u g e se,   a n d   A r a b i c   n a m e s   S i mi l a r i t y   me a n   0 . 9 0   F - M e a s u r e   mea n   0 . 9 1   2 0 2 0   [ 1 6 ]     B y t e   p a i r   e n c o d i n g   En g l i sh - J a p a n e se   W i k i p e d i a   M o d e l   t r a i n e d   w i t h   U n i g r a m   LM   p e r f o r me d   b e t t e r   2 0 2 2   [ 1 7 ]   B y t e   p a i r   e n c o d i n g   Ge r man - E n g l i sh ,   R u ss i a n - E n g l i s h ,   a n d   R o m a n i a n - E n g l i s h   W M T 2 0 2 0 ,   W M T 2 0 1 6 ,   W M T 2 0 1 7   B P a l g o r i t h m w a s   q u i t e   u sef u l   i n   t r a n s l a t i n g   O O V   w o r d i n   t h e   d a t a se t   2 0 2 2   [ 6 ]   D a mera u   L e v e n s h t e i n   d i s t a n c e   a n d   N - g r a m   A maz i g h   A maz i g h   c o r p u s   F - mea su r e   r a n g e d   f r o m   8 6 . 6 2 %   t o   9 8 . 7 4 %   2 0 2 2   [ 1 1 ]   Tr i e   a n d   d e p t h - f i r s t   sea r c h   I n d o n e si a n   I n d o n e si a n   D i c t i o n a r y   I mp l e me n t i n g   s e a r c h   su g g e st i o n b a s e d   o n   n o d e   l o c a t i o n   i n   t h e   t e st i n g   2 0 2 3   [ 7 ]   B ER T - b a se d   ma sk e d   l a n g u a g e   mo d e l   a n d   e d i t   d i s t a n c e   En g l i sh   N e u s p e l l   d a t a s e t   R e c a l l   8 1 . 2 1 %   2 0 2 3   [ 1 2 ]   M i n i m u m   e d i t   d i s t a n c e   a n d   c o s i n e   s i mi l a r i t y   M a r a t h i   M a r a t h i   d o c u me n t s   M ED   a c c u r a c y   8 5 . 8 8 %   C o s i n e   a c c u r a c y   8 6 . 7 6 %   2 0 2 3   [ 1 8 ]   Le v e n s h t e i n   e d i t   d i s t a n c e   a n d   s t r i n g - m a t c h i n g   a l g o r i t h m   B e n g a l i   B e n g a l i   d o c u me n t s   A c c u r a c y   9 2 . 4 0 4 %   2 0 2 3   [ 1 9 ]   D a mera u   L e v e n s h t e i n   d i s t a n c e   K a z a k h   K a z a k h   t e x t s   A c c u r a c y   9 2 . 8   %.       3.   M E T H O D   T h is   s ec tio n   d escr ib ed   th co m b in atio n   o f   L ev en s h tein   d is t an ce   an d   T r ie   alg o r ith m   as  th m eth o d .   T h is   co m b in ati o n   m eth o d   u s ed   to   e v alu atin g   tex t   co r r e ctio n s   to   o b tain   ap p r o p r iate  tr an s latio n   r esu lts .     Fig u r 1   illu s tr ated   th f o llo wi n g   s tep s   o f   th r esear c h   m eth o d .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J I n f   &   C o m m u n   T ec h n o l     I SS N:   2252 - 8 7 7 6       E va lu a tio n   o f te xt  co r r ec tio n   u s in g   a   co mb in a tio n   o L ev en s h tein   d is ta n ce   a n d   Tr ie   … ( C yn th ia   N a ta lie )   1343   3 . 1 .     Da t a   c o llect io n   I n   th e   d ata   co llectio n   s ec tio n ,   d ata  u s ed   in   th is   r esear ch   i n clu d es  th e   I n d o n esian   la n g u a g d ictio n ar y   as  co m p ar is o n   to   th in p u tex u s in g   th k b b i - p y th o n   lib r ar y   an d   2 0 0   in p u tex d ata  co llected   f r o m   I n d o n esian   n ews  with   v ar io u s   s p ellin g   er r o r s   [ 2 0 ] .   T h e   s p ellin g   er r o r s   wer e   g en e r ated   b y   m ac h in e   p r ev io u s ly   p r o ce s s ed   in   r esear ch   co n d u cted   in   2 0 2 0 ,   ca teg o r ized   b ased   o n   t h tex len g t h s h o r tex t,  m ed iu m   tex t,  an d   lo n g   tex t.   T o tal  am o u n o f   in p u tex t   d ata  u s ed   is   2 0 0   c o n tain s   o f   5 7 . 0 9 8   w o r d s ,   co n s is tin g   o f   1 0 0   tex ts   with o u s p ellin g   er r o r s   an d   1 0 0   tex ts   with   v ar io u s   ty p es  o f   s p ellin g   er r o r s ,   s p ec if ically   lex ical  er r o r s ,   with   3 0 % tr ain in g   a n d   7 0 % testi n g   d ata,   am o u n tin g   to   1 4 0   tr ain in g   d ata  a n d   6 0   test i n g   d ata           Fig u r 1 .   R esear ch   m eth o d       3 . 2 .     Da t a   prepro ce s s ing   B ef o r p r o ce s s in g   d ata  u s in g   th co m b in ati o n   o f   L ev e n s h te in   d is tan ce   an d   T r ie   alg o r ith m ,   th tex d ata  m u s t g o   th r o u g h   p r ep r o ce s s in g   s tep s .   Pre p r o ce s s in g   u s ed   to   r em o v e   d ata  i n co n s is ten cies  in   th e   f o llo win g   s tep s ,   s u ch   as  p ar s in g ,   ca s f o l d in g ,   an d   to k en izin g .   I n   th is   co n tex t,  th p r e p r o ce s s in g   s tep s   d o   n o co r r ec th e   tex t d ata   [2 1 ] .   T h e   p r e p r o ce s s in g   s tep s   illu s tr ated   in   Fig u r 2   [ 2 2 ]           Fig u r 2 Data   p r ep r o ce s s in g       3 . 1 .     T RIE   AP P L I CAT I O N   I n   Alg o r ith m   1   T r ie   d ata  s tr u ctu r ca n   b ap p lied   b y   c r ea tin g   class   to   s ea r ch   f o r   tex w ith   s im ilar   p r ef ix es   [ 2 3 ] .   T h e   p u r p o s is   f o r   g r o u p in g   s ev er al  te x ts   th at  h av e   s im ilar ities   with   an   ac c u r ac y   o f   m o r e   th a n   5 0 % to   p r o ce ed   to   th n e x t step   [2 4 ]     Alg o r ith m   1 .   T r ie   d ata  s tr u ctu r alg o r ith m   class  Trie Node:        def __init__(self):            self.children = {}            self.is_end_of_word = False            self.frequency = 0      class  Trie :        def __init__(self):            self.root =  Trie Node()           def insert(self, word):            node = self.root            for char in word:                if char not in node.children:                    node.children[char] =  Trie Node()                node = node.children[char]            node.is_end_of_word = True   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8 7 7 6   I n t J I n f   &   C o m m u n   T ec h n o l ,   Vo l.  15 ,   No .   3 Sep tem b er   20 26 1 3 4 0 - 1 3 5 1   1344            node .frequency += 1        def search(self, word):            node = self.root            for char in word:                if char not in node.children:                    return False                node = node.children[char]            return node.is_end_of_word     Ap p ly in g   T r ie   d ata  s tr u ctu r es  s p ee d   u p   s ea r ch in g   tim e. b ased   o n   s im ilar   p r ef i x es.  T r ie   d ata  s tr u ctu r es  g r o u p ed   all   wo r d s   with   th e   s am p r e f ix   s to r e d   in   th e   lis o f   t ex ts .   Fo r   e x am p le,   T r ie   d ata  s t r u ctu r es  ap p lied   as   s h o wn   in   T ab le  2 .   As  s h o wn   in   T ab le  2 ,   ea ch   te x d ata,   wh eth er   with   o r   with o u s p ellin g   er r o r s ,   h ad   g r o u p ed   s im ilar   tex d ata  to   th in p u tex in   p u r p o s to   f in d   tex ts   with   th s am p r ef ix .   T r ie   d ata  s tr u ctu r s ea r ch ed   i n   I n d o n esian   lan g u ag d ictio n a r y   u s in g   th e   wo r d   o f   ay a n   b ased   o n   two   p r ef ix es  t o   f in d   all  wo r d s   with   th e   s am ay   p r ef ix .   T h s am p r ef ix es st o r ed   in   th lis t   o f   te x ts   b ef o r e   m o v e   th r o u g h   n ex t ste p .       T ab le  2 .   T r ie   d ata  s tr u ctu r a p p licatio n   Te x t   S p e l l i n g   e r r o r   t e x t   R i g h t   t e x t   Tr i e   d a t a   st r u c t u r e   a y a n   ( Fa l se )   a y a n   ( Fa l se )   a y a m ( T ru e )   a y a h   |   a y a m |   a y a n   |   a y o m   b a l i   ( T r u e )     b a l i   ( T r u e )   b a l i   |   b a l i k   |   b a l i t a   b e t u t u   ( T ru e )     b e t u t u   ( T ru e )   b e t u l   |   b e t u t u   d i m a sa  ( T r u e )     d i m a sa  ( T r u e )   d i m a sa  |   d i mas a k   |   d i mas u k i       3 . 3 .     L ev ens hte in dis t a nce   T h ca lcu latio n   o f   th L e v en s h tein   d is tan ce   alg o r ith m   is   p e r f o r m e d   u s in g   s tr in g   o p e r atio n s   s u ch   as   in s er tio n ,   d eletio n ,   an d   s u b s ti tu tio n   to   co m p u te  th e   ch ar ac t er   d is tan ce   [ 1 5 ] L ev e n s h tein   d is tan ce   alg o r ith m   ca lcu lated   b etwe en   th e   in p u tex an d   th e   lis o f   tex ts   to   f i n d   m i n im u m   ch ar ac te r   d is tan ce   an d   d is p lay   th e   co r r ec ted   tex b ased   o n   th e   m i n im u m   c h ar ac ter   d is tan ce   [ 2 5 ] .   T h e   d is tan ce   is   d eter m in e d   b y   th e   ( 1 ) ,   ( 2 ) ,   an d   ( 3 )   f u n ctio n   b elo w.        , ( , ) =   {             0                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         {  , ( 1 , ) + 1                                                                                                                                                                                                                                       ( 1 )  , ( , 1 ) + 1                                                                                                                                                                                                                                       ( 2 )  , ( 1 , 1 ) + 1   [ ]                                                                                                                                                                                   ( 3 )     T h f u n ctio n   o f   th L ev en s h te in   d is tan ce   alg o r ith m   in   ( 1 ) ,   ( 2 ) ,   an d   ( 3 )   im p lem en ted   o n   tw o   ex am p le  s tr in g s   ( s tr in g   A:   ay an ;   s tr in g   B ay am ) .   All  ch ar ac ter s   in   b o th   s tr in g s   c o m p ar e d   ea c h   o th e r   to   f in d   eith er   th e   ch ar ac ter   is   th s am o r   n o b y   u s in g   L ev e n s h tein   d is tan ce   ca lcu latio n .   Af ter war d s ,   ca lc u latio n   tab le  ca n   b e   g en er ated   as sh o wn   in   T ab le  3 .       T ab le  3 .   L e v en s h tein   d is tan ce   alg o r ith m   ca lcu latio n   P o si t i o n   C h a r a c t e r   1   C h a r a c t e r   2   D i st a n c e s   F o r mu l a   R e s u l t   D ( 1 , 1 )   a   a   Th e r e   i s n t   a n y   D(1 - 1 , 1 - 1)   0   D ( 1 , 2 )   a   y   Th e r e   i s   D ( 1 , 2 - 1 ) + 1   1   D ( 1 , 3 )   a   a   Th e r e   i s n t   a n y   D(1 - 1 , 3 - 1)   2   D ( 1 , 4 )   a   m   Th e r e   i s   D ( 1 , 4 - 1 ) + 1   3   D ( 2 , 1 )   y   a   Th e r e   i s   D ( 2 , 1 - 1 ) + 1   1   D ( 2 , 2 )   y   y   Th e r e   i s n t   a n y   D(2 - 1 , 2 - 1)   0   D ( 2 , 3 )   y   a   Th e r e   i s   D ( 2 , 3 - 1 ) + 1   1   D ( 2 , 4 )   y   m   Th e r e   i s   D ( 2 , 4 - 1 ) + 1   2   D ( 3 , 1 )   a   a   Th e r e   i s n t   a n y   D(3 - 1 , 1 - 1)   1   D ( 3 , 2 )   a   y   Th e r e   i s   D ( 3 , 2 - 1 ) + 1   2   D ( 3 , 3 )   a   a   Th e r e   i s n t   a n y   D(3 - 1 , 3 - 1)   0   D ( 3 , 4 )   a   m   Th e r e   i s   D ( 3 , 4 - 1 ) + 1   1   D ( 4 , 1 )   n   a   Th e r e   i s   D ( 4 , 1 - 1 ) + 1   2   D ( 4 , 2 )   n   y   Th e r e   i s   D ( 4 , 2 - 1 ) + 1   2   D ( 4 , 3 )   n   a   Th e r e   i s   D ( 4 , 3 - 1 ) + 1   1   D ( 4 , 4 )   n   m   Th e r e   i s   D ( 4 , 4 - 1 ) + 1   1   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J I n f   &   C o m m u n   T ec h n o l     I SS N:   2252 - 8 7 7 6       E va lu a tio n   o f te xt  co r r ec tio n   u s in g   a   co mb in a tio n   o L ev en s h tein   d is ta n ce   a n d   Tr ie   … ( C yn th ia   N a ta lie )   1345   B ased   o n   th r esu lts   o f   th L e v en s h tein   d is tan ce   alg o r ith m   ca lcu latio n   in   T ab le  3 ,   t h m a tr ix   ca n   b f illed   in   ac co r d in g   to   ch ar ac t er   p o s itio n .   E ac h   co lu m n s   d e f in ed   ch ar ac ter   1   as  th tex t   with   s p ellin g   er r o r   an d   ea ch   r o ws  d ef in ed   ch a r a cter   2   as  th wo r d   f r o m   th lis o f   tex ts   g en er ated   f r o m   T r ie   da ta  s tr u ctu r e.   Fin al  m atr ix   g en er ated   as  s h o wn   in   T ab le  4 B ased   o n   T ab le  4 ,   it  ca n   b s ee n   th at  D( 4 ,   4 )   1 ,   s h o win g   th at  th er is   o n c h ar ac ter   d if f e r en ce   o u t   o f   th e   f o u r   c h ar ac ter s   co m p ar ed .   T h wo r d   s im ilar ity   s co r e   ca lcu latio n   r esu lt  is   7 5 %.  W ith   th is   s co r e,   th co m b i n atio n   alg o r ith m   h ad   d is p lay ed   s u g g esti o n s   in   th tex co r r ec tio n   r ec o m m en d atio n   tab le  f o r   u s er   to   ch o o s o n as th co r r ec t te x t c o r r ec tio n   [ 2 6 ] .   T h u s ,   ac cu r ate  tex t c o r r ec tio n   r esu lted   in   g o o d   a n d   c o r r ec tex t tr an s latio n .       T ab le  4 .   L e v en s h tein   d is tan ce   alg o r ith m   r esu lt     -   a   y   a   n   -   0   1   2   3   4   a   1   0   1   2   3   y   2   1   0   1   2   a   3   1   2   0   1   m   4   2   2   1   1       3 . 4 .     L ev ens hte in dis t a nce   a n T rie   a lg o rit hm   I m p lem en tatio n   o f   L ev e n s h tein   d is tan ce   an d   T r ie   alg o r ith m s   is   p er f o r m e d   u s in g   Py th o n   p r o g r a m m in g   la n g u a g e.   T h is   im p lem en tatio n   r e q u ir ed   a n   in p u tex in   p u r p o s to   b co r r e cted   an d   g en e r ated   tr an s lated   tex as  th o u tp u t.   T h tex c o r r ec tio n   f lo wc h a r ca n   b e   s ee n   in   Fig u r 3 .   B ased   o n   Fig u r 3 ,     tex c o r r ec tio n   is   ca r r ied   o u t   b y   in p u ttin g   tex in   th co n tex o f   lan g u ag tr an s latio n .   Sp ellin g   er r o r s   h ad   d etec ted   in   th in p u tex an d   i f   s p ellin g   er r o r   is   d etec ted ,   T r ie   d ata  s tr u ctu r s ea r ch   b ased   o n   s im ilar   p r ef ix es   [ 1 4 ] .   Fu r th er m o r e,   T r ie   s ea r ch   r esu lts   s to r ed   in   lis t to   b ca lcu lated   u s in g   L ev e n s h tein   d is tan ce   alg o r ith m .   T h is   ex p er im e n co llected   d at aset  in   I n d o n esian   lan g u a g an d   s p litt ed   i n to   3 0 tr ain in g   d ata   an d   7 0 test in g   d ata  as  m en tio n ed   in   s u b - s ec tio n   3 . 1   [ 2 0 ] .   Data s et  h ad   to   b p r o ce s s ed   in   p r ep r o ce s s in g   s tag to   g et  clea n s ed   d ataset  an d   ca n   b p r o p e r ly   p r o ce s s ed   b y   th s y s tem .   At  th i s   s tag e,   th p r e p r o ce s s in g   p r o ce s s   wo u ld   n o d ir ec tly   co r r ec s p ellin g   er r o r   m a r k ed   b y   r ed   in   T ab le  5   an d   o n ly   clea n   th tex d ata  in to   n o r m alize d   tex d ata.     T h is   s tag is   co n d u cted   in   s ev er al  s tep s ,   s u ch   as  p ar s in g ,   ca s f o ld in g ,   an d   to k en izin g .   T ex t p r ep r o ce s s in g   r esu lts   ar also   s h o wn   in   T ab le  5 .           Fig u r 3 .   Pro ce s s   f lo wch a r t       T ab le  5 .   Pre p r o ce s s in g   r esu lt   Te x t   P a r si n g   C a se   F o l d i n g   To k e n i z i n g   Jo sh   Ea r n e s t   m e n y a t a k a n   t i d a k   m u n g k i n   A m e r i k a   S e r i k a t   me n g e r a h k a n   p a s u k a n   l a g i   k e   I r a k .   Jo sh   Ea r n e s t   m e n y a t a k a n   t i d a k   m u n g k i n   A m e r i k a   S e r i k a t   me n g e r a h k a n   p a s u k a n   l a g i   k e   I r a k .   j o s h   e a r n e st   me n y a t a k a n   t i d a k   m u n g k i n   a mer i k a   seri k a t   me n g e r a h k a n   p a s u k a n   l a g i   k e   i r a k   [ j o sh ,   e a r n e s t ,   m e n y a t a k a n ,   t i d a k ,   m u n g k i n ,   a m e r i k a ,   seri k a t ,   me n g e r a h k a n ,   p a su k a n ,   l a g i ,   k e ,   i r a k ]   J o s h   E a r n e s t   s t t e d   t h a t   i t   i n o t   p o ssi b l e   f o t h e   U n i t e d   S t a t e t o   d e p l o y   t ro o p t o   I ra q   a g a i n .   J o s h   E a r n e s t   s t t e d   t h a t   i t   i n o t   p o ssi b l e   f o t h e   U n i t e d   S t a t e t o   d e p l o y   t ro o p t o   I ra q   a g a i n .   j o s h   e a r n e s t   s t t e d   t h a t   i t   i n o t   p o ssi b l e   f o t h e   u n i t e d   st a t e t o   d e p l o y   t r o o p t o   i ra q   a g a i n .   [ j o sh ,   e a r n e st ,   st t e d ,   t h a t ,   i t ,   i s’ ,   n o t ,   p o ss i b l e ,   f o r’ ,   t h e ,   u n i t e d ,   st a t e s’ ,   t o ,   d e p l o y ,   t ro o p s’ ,   t o ,   i ra q ,   a g a i n ]       T r ie   d ata  s tr u ctu r is   ap p lied   t o   s ea r ch   f o r   tex d ata  with   s im ilar   p r ef ix es  in   th d ictio n a r y   u s ed   as  co m p ar is o n   f o r   tex co r r ec tio n   p u r p o s es   [ 2 4 ] L ev en s h tein   d is tan ce   alg o r ith m   ca lcu lated   to   f in d   th s m allest  d is tan ce   b etwe en   th o r ig in al  tex an d   th lis o f   tex ts   f r o m   th d ictio n ar y   u s ed   a f ter   s ea r ch in g   f o r   tex d ata   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8 7 7 6   I n t J I n f   &   C o m m u n   T ec h n o l ,   Vo l.  15 ,   No .   3 Sep tem b er   20 26 1 3 4 0 - 1 3 5 1   1346   with   s im ilar   p r ef ix es  u s in g   T r ie   d ata  s tr u ctu r e   to   f in d   th e   s m allest  d is tan ce   in   th e   p u r p o s o f   tex co r r ec tio n .   L ev en s h tein   d is tan ce   ca lcu lat io n   r esu lted   as  s h o wn   in   T a b le  6 .   L ev e n s h tein   d is tan ce   alg o r ith m   u s ed   to   ca lcu late  th s m allest  d i s tan c b etwe en   I n d o n esian   tex ts   as  s h o wn   in   T ab le  6 .   Af ter   th ca lcu latio n   r esu lts   o b tain ed ,   th d is tan ce   b etwe e n   tex ts   s o r ted   f r o m   t h s m allest  d is tan ce   o b tain ed   to   th lar g est  d is tan ce   in   th s u g g esti o n   lis d is p lay ed .   T h to p   c o r r ec tio n   r esu lt  is   d is p lay ed   as  th e   b est  m atch es  t ex co r r ec tio n   to   th e   in p u tex t   as  in   T ab le   7 .   B ased   o n   T a b le  7 ,   it   ca n   b s ee n   th at   s u g g es tio n s   s o r te d   b ased   o n   L e v en s h tein   d is tan ce   ca lcu latio n   d is tan ce   as  th r esu lt  o f   tex c o r r ec tio n . .   I s h o wn   th at   f ir s s u g g est io n   h a d   t h s h o r test   d is tan ce   u s in g   th co m b in ati o n   o f   L ev e n s h tein   d is tan ce   an d   T r ie   alg o r ith m .   First  s u g g esti o n   o f   th to p   s u g g es tio n s   s elec ted   as th r esu lt o f   tex t c o r r ec tio n ,   tr an s lated   an d   d is p lay ed   as tr an s lated   t ex t.       T ab le  6 .   L e v en s h tein   d is tan ce   ca lcu latio n   r esu lts   P o si t i o n   C h a r a c t e r   1   C h a r a c t e r   2   D i st a n c e s   F o r mu l a   R e s u l t   d [ 1 ]   [ 1 ]   j   j   Th e r e   i s n t   a n y   d [ 1 - 1 ]   [ 1 - 1]   0   d [ 1 ]   [ 2 ]   j   o   Th e r e   i s   d [ 1 ]   [ 2 - 1 ]   +   1   1   d [ 1 ]   [ 3 ]   j   s   Th e r e   i s   d [ 1 ]   [ 3 - 1 ]   +   1   2   d [ 1 ]   [ 4 ]   j   h   Th e r e   i s   d [ 1 ]   [ 4 - 1 ]   +   1   3   d [ 1 ]   [ 5 ]   j     Th e r e   i s   d [ 1 ]   [ 5 - 1 ]   +   1   4   d [ 1 ]   [ 6 ]   j   e   Th e r e   i s   d [ 1 ]   [ 6 - 1 ]   +   1   5   d [ 1 ]   [ 7 ]   j   a   Th e r e   i s   d [ 1 ]   [ 7 - 1 ]   +   1   6   d [ 1 ]   [ 8 ]   j   r   Th e r e   i s   d [ 1 ]   [ 8 - 1 ]   +   1   7   d [ 1 ]   [ 9 ]   j   n   Th e r e   i s   d [ 1 ]   [ 9 - 1 ]   +   1   8   d [ 1 ]   [ 1 0 ]   j   e   Th e r e   i s   d [ 1 ]   [ 1 0 - 1 ]   +   1   9   d [ 1 ]   [ 1 1 ]   j   s   Th e r e   i s   d [ 1 ]   [ 1 1 - 1 ]   +   1   10   d [ 1 ]   [ 1 2 ]   j   t   Th e r e   i s   d [ 1 ]   [ 1 2 - 1 ]   +   1   11   d [ 1 ]   [ 1 3 ]   j     Th e r e   i s   d [ 1 ]   [ 1 3 - 1 ]   +   1   12   d [ 1 ]   [ 1 4 ]   j   m   Th e r e   i s   d [ 1 ]   [ 1 4 - 1 ]   +   1   13   d [ 1 ]   [ 1 5 ]   j   e   Th e r e   i s   d [ 1 ]   [ 1 5 - 1 ]   +   1   14   d [ 1 ]   [ 1 6 ]   j   n   Th e r e   i s   d [ 1 ]   [ 1 6 - 1 ]   +   1   15   d [ 1 ]   [ 1 7 ]   j   y   Th e r e   i s   d [ 1 ]   [ 1 7 - 1 ]   +   1   16   d [ 1 ]   [ 1 8 ]   j   a   Th e r e   i s   d [ 1 ]   [ 1 8 - 1 ]   +   1   17   d [ 1 ]   [ 1 9 ]   j   t   Th e r e   i s   d [ 1 ]   [ 1 9 - 1 ]   +   1   18   d [ 1 ]   [ 2 0 ]   j   a   Th e r e   i s   d [ 1 ]   [ 2 0 - 1 ]   +   1   19   d [ 1 ]   [ 2 1 ]   j   k   Th e r e   i s   d [ 1 ]   [ 2 1 - 1 ]   +   1   20   d [ 1 ]   [ 2 2 ]   j   a   Th e r e   i s   d [ 1 ]   [ 2 2 - 1 ]   +   1   21   d [ 1 ]   [ 2 3 ]   j   n   Th e r e   i s   d [ 1 ]   [ 2 3 - 1 ]   +   1   22           ….         T ab le  7 .   So r te d   s u g g esti o n s   te x t   R a n k   O r i g i n a l   T e x t   S u g g e s t i o n   T e x t   b a s e d   o n   D i c t i o n a r y   D i st a n c e s   1 st   j o s h   e a r n e st   me n y t a k a n   t i d a k   mu n g k i n   a meri k a   seri k a t   m e n g e r a h k a n   p a su k a n   l a g i   k e   i r a k   j o s h   e a r n e st   me n y a t a k a n   t i d a k   m u n g k i n   a mer i k a   s e r i k a t   men g e r a h k a n   p a s u k a n   l a g i   k e   i r a k   ( su g g e s t e d )   j o s h   e a r n e s t   s t t e d   t h a t   i t   i n o t   p o ssi b l e   f o t h e   u n i t e d   st a t e t o   d e p l o y   t ro o p t o   i r a q   a g a i n .   j o s h   e a r n e s t   s t a t e d   t h a t   i t   i n o t   p o ssi b l e   f o t h e   u n i t e d   st a t e t o   d e p l o y   t r o o p t o   i r a q   a g a i n .   2 n d   j o s h   e a r n e st   me n y t a k a n   t i d a k   mu n g k i n   a meri k a   seri k a t   m e n g e r a h k a n   p a su k a n   l a g i   k e   i r a k   seri k a t   p e k e r j a   j a k a r t a   i n t e r n a t i o n a l   s c h o o l   j i s m e n d a t a n g i   k o m i si   k e p o l i s i a n   n a s i o n a l   k o mp o l n a s   u n t u k   me l a y a n g k a n   p e n g a d u a n ……   1 5 4 1   j o s h   e a r n e s t   s t t e d   t h a t   i t   i n o t   p o ssi b l e   f o t h e   u n i t e d   st a t e t o   d e p l o y   t ro o p t o   i r a q   a g a i n .   t h e   j a k a r t a   i n t e rn a t i o n a l   sc h o o l   ( j i s)   w o r k e rs   u n i o n   v i si t e d   t h e   n a t i o n a l   p o l i c e   c o m m i ssi o n   ( k o m p o l n a s)   t o   f i l e   a   c o m p l a i n t     3 r d   j o s h   e a r n e st   me n y t a k a n   t i d a k   mu n g k i n   a meri k a   seri k a t   m e n g e r a h k a n   p a su k a n   l a g i   k e   i r a k   seri k a t   p e k e r j a   j a k a r t a   i n t e r n a t i o n a l   s c h o o l   j i s m e n d a t a n g i   k o m i si   k e p o l i s i a n   n a s i o n a l   k o mp o l n a s   u n t u k   me n g a d u k a n   k e b e r a t a n   2 0 9 7   j o s h   e a r n e s t   s t t e d   t h a t   i t   i n o t   p o ssi b l e   f o t h e   u n i t e d   st a t e t o   d e p l o y   t ro o p t o   i r a q   a g a i n .   t h e   j a k a r t a   i n t e rn a t i o n a l   sc h o o l   ( j i s)   w o r k e rs   u n i o n   v i si t e d   t h e   n a t i o n a l   p o l i c e   c o m m i ssi o n   ( k o m p o l n a s)   t o   l o d g e   a   c o m p l a i n t         4.   RE SU L T S AN D I SCU SS I O N   T h is   r esear ch   co n d u cted   in   o r d er   to   e v alu atin g   t h co m b in atio n   o f   L ev en s h tein   d is tan ce   an d   T r i e   alg o r ith m   in   th co n tex o f   te x co r r ec tio n .   Pre v io u s   r esear ch   h av e   p r o p o s ed   v ar io u s   m et h o d s   to   h an d le  te x co r r ec tio n   p r o b lem s ,   h o wev er ,   th er e’ s   lim itatio n   o f   th p r ev io u s   r esear ch ,   s u ch   as  ex ce s s i v wo r d   co r r ec tio n   r esu lts   ca u s ed   o f   u n g r o u p ed   wo r d ,   im p r ec is wo r d   s u g g es tio n s ,   an d   h ig h   m em o r y   u s ag e.   W f o u n d   th at   en h an cin g   L ev e n s h tein   d is tan ce   an d   T r ie   alg o r ith m   c o u ld   lead   to   m o r ef f icien tex c o r r ec tio n .   T r ie   d ata   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J I n f   &   C o m m u n   T ec h n o l     I SS N:   2252 - 8 7 7 6       E va lu a tio n   o f te xt  co r r ec tio n   u s in g   a   co mb in a tio n   o L ev en s h tein   d is ta n ce   a n d   Tr ie   … ( C yn th ia   N a ta lie )   1347   s tr u ctu r es  r ed u ce d   m em o r y   u s ag in   g r o u p i n g   b ased   o n   s im ilar   p r ef ix es,  co m b in e d   with   L ev e n s h tein   d is tan ce   to   ca lcu late  d is tan ce .   As m en tio n ed   in   s u b - s ec tio n   3 . 1 ,   d ataset  u s ed   in   co n s is tin g   o f   1 0 0   te x ts   with o u t sp ellin g   er r o r s   an d   1 0 0   te x ts   with   v ar i o u s   ty p es  o f   s p ellin g   er r o r s .   A f ter   th e x p er im e n d o n e,   e v al u atio n   m ea s u r e d   b y   ca lcu latin g   p er f o r m a n ce   ev alu atio n   m etr ics.        5.   CO NF USI O M AT RIX  E V AL UA T I O N   E v alu atio n   m ea s u r e d   b y   ca lcu latin g   ac cu r ac y ,   p r ec is io n ,   r ec all  an d   F - m ea s u r as  th p er f o r m a n ce   ev alu atio n   m etr ics.  Pre cisi o n   is   d ef in e d   as  t h n u m b e r   o f   c o r r ec tly   d etec ted   s p ellin g   er r o r s   c o m p ar e d     to   all  d etec ted   s p ellin g   er r o r s .   R ec all  is   d ef in ed   as  th e   n u m b er   o f   co r r ec tly   d etec t ed   s p ellin g   er r o r s     d iv id ed   b y   th e   to tal  n u m b e r   o f   c o r r ec ted   tex t   in   t h d ataset.   T h e   ex p e r im en tal  r esu lts   s h o wn   in   T ab le   8 .     T h p er f o r m an ce   ev alu atio n   m etr ics  h av to   b co m p a r ed   t o   o th er   alg o r ith m   co m b in atio n s   as  b en ch m ar k in g .   E v alu atio n   r esu lts   o f   t h co m b in atio n   o f   L e v en s h tein   d is tan ce   an d   T r ie   alg o r ith m   u s in g   th e   C o n f u s io n   Ma tr ix   ar s h o wn   in   T a b le  9 .         T ab le  8 .   E x p er im en tal  r esu lts   u s in g   th co m b in atio n   o f   L e v e n s h tein   d is tan ce   an d   T r ie   Ev a l u a t i o n   R e s u l t   To t a l   e r r o r i n   d a t a se t   4 0 0   D e t e c t e d   s p e l l i n g   e r r o r a n d   c o r r e c t e d   ( TP)   1 9 2   D e t e c t e d   s p e l l i n g   e r r o r a n d   n o t   c o r r e c t e d   ( F N )   8   N o t   d e t e c t e d   sp e l l i n g   e r r o r s   a n d   c o r r e c t e d   ( F P )   63   N o t   d e t e c t e d   sp e l l i n g   e r r o r s   a n d   n o t   c o r r e c t e d   ( TN )   1 3 7   R e c a l l   r a t e   1 9 2 / ( 1 9 2 + 8 )   =   0 . 9 6 0 0   P r e c i s i o n   r a t e   1 9 2 / ( 1 9 2 + 6 3 )   =   0 . 7 5 2 9   F 1   S c o r e   r a t e   2 ( 0 . 9 6 0 0 ) ( 0 . 7 5 2 9 ) / ( 0 . 9 6 0 0 + 0 . 7 5 2 9 )   =   0 . 8 4 3 9       T ab le  9 .   C o n f u s io n   m atr ix   ev a lu atio n   Ev a l u a t i o n   LD   a n d   Tr i e   ( P r o p o se d )   LD   a n d   N - G r a m   [ 1 5 ]   LD   a n d   R a b i n   K a r p   [ 1 0 ]   A c c u r a c y   0 . 8 2 2 5   0 . 7 5 0 0   0 . 2 8 2 5   R e c a l l   0 . 9 6 0 0   0 . 5 0 0 0   0 . 5 0 5 0   P r e c i s i o n   0 . 7 5 2 9   1 . 0 0 0 0   0 . 3 4 9 5   F 1   S c o r e   0 . 8 4 3 9   0 . 6 6 6 7   0 . 4 1 3 1       B ased   o n   T ab le   9 ,   t h ev al u atio n   was  co n d u cted   to   m ea s u r e   th p e r f o r m an ce   o f   t h co m b in atio n   o f   L ev en s h tein   d is tan ce   alg o r ith m   an d   T r ie   in   tex co r r ec tio n   b y   ca lcu latin g   ac cu r ac y ,   r ec al l,  p r ec is io n ,   an d   F 1   s co r e.   T h is   e v alu atio n   co m p ar ed   with   th c o m b in atio n   o f   o th er   alg o r ith m   co m b in at io n s ,   s u ch   as  th e   co m b in atio n   o f   L ev en s h tein   d is tan ce   an d   N - Gr am ,   an d   th co m b in atio n   o f   L ev e n s h tein   d is t an ce   an d     R ab in - Kar p   alg o r ith m .   Fro m   th r esu lt  illu s tr ated   in   T ab le  9 ,   we  f o u n d   th at  th co m b in at io n   o f   L ev en s h tein   d is tan ce   an d   T r ie   p er f o r m s   b et ter   th an   th o th er   alg o r ith m   c o m b in atio n s .     5 . 1 .     AUC - RO ev a lua t io n   T h ev alu atio n   r esu lts   ca n   b v is u alize d   u s in g   t h r esh o l d   s ettin g s   with   th e   AUC  R OC   cu r v e.   T h er ef o r e,   ca lcu latio n s   wer p er f o r m ed   u s in g   t h v alu es  g en er ated   f r o m   th co n f u s io n   m atr ix   to   ca lcu late   tr u p o s itiv r ate  ( T PR )   an d   f a ls p o s itiv r ate  ( FP R ) .   T h c alcu latio n   r es u lts   ar s h o wn   in   T ab le  1 0 .       T ab le  1 0 .   T PR - FP R   ca lcu lat io n   Th r e s h o l d   TPR   FPR   0 . 1   0 . 0 1 0 2 0 4   0 . 3 4 9 0 5 7   0 . 2   0 . 0 3 3 8 3 5   0 . 5 2 9 8 5 1   0 . 3   0 . 0 7 0 2 4 8   0 . 6 5 1 8 9 9   0 . 4   0 . 1 0 7 4 7 7   0 . 7 3 6 5 5 9   0 . 5   0 . 1 7 6 7 6 8   0 . 8 1 6 8 3 2   0 . 6   0 . 2 4 4 1 8 6   0 . 8 6 8 4 2 1   0 . 7   0 . 3 3 5 6 1 6   0 . 9 0 9 4 4 9   0 . 8   0 . 4 6 8 7 5   0 . 9 5 5 8 8 2   0 . 9   0 . 6 6 3 2 6 5   0 . 9 7 6 8 2 1   1 . 0   1   1       Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8 7 7 6   I n t J I n f   &   C o m m u n   T ec h n o l ,   Vo l.  15 ,   No .   3 Sep tem b er   20 26 1 3 4 0 - 1 3 5 1   1348   B ased   o n   T ab le  1 0 ,   th e   AUC  R OC   cu r v ca n   b c r ea ted   u s i n g   th ca lc u lated   tr u e   p o s itiv e   r ate  ( T PR )   an d   f alse  p o s itiv r ate  ( FP R ) .   T h h ig h er   T PR   v alu is ,   it   ca n   b s ee n   th at  th co m b in atio n   o f   L ev en s h tein   d is tan ce   an d   T r ie   alg o r ith m   p r o v id b etter   r esu lts   th an   th o th er   co m b in atio n   in   th co n tex t   o f   te x co r r ec tio n .   AUC - R O C   C u r v ar s h o wn   in   Fig u r 4 .           Fig u r 4 .   AUC - R OC   C u r v e       5 . 2 .     B leu sco re   ev a lua t io n   E v alu atio n   r esu lts   ca n   b e   en h an ce d   to   m ea s u r t h q u ality   o f   tr an s latio n   r esu lts   af ter   tex t   co r r ec tio n   b y   ca lcu latin g   th b ilin g u al  e v alu atio n   u n d er s tu d y   s co r ( B L E U )   u s in g   Un ig r am   Pre cisi o n .   Go o d   tr an s latio n   q u ality   ca n   b p r o v e n   b y   B L E s co r a p p r o ac h in g   to   1 .   As  s h o wn   in   T ab le   1 1 ,   B L E s co r in c r ea s ed   b y   0 . 0 1 5 5   o r   ab o u t 1 . 5 5 % a f ter   te x t c o r r ec tio n   was p er f o r m ed .       T ab le  1 1 .   B L E s co r e v alu at io n   Ev a l u t i o n   B LEU   s c o r e   B LEU   S c o r e   b e f o r e   t e x t   c o r r e c t i o n   0 . 6 6 0 2   B LEU   S c o r e   a f t e r   t e x t   c o r r e c t i o n   0 . 6 7 5 7       6.   CO NCLU SI O N   B ased   o n   th r esu lts   an d   d is c u s s io n s   th at  h av b ee n   co n d u cted ,   th r esear ch   s u cc ess f u lly   d ev elo p ed   an d   ev alu ate d   tex co r r ec tio n   u s in g   co m b in atio n   o f   L ev e n s h tein   d is tan ce   alg o r ith m   to   m ea s u r th d is tan ce   b etwe en   tex ts ,   u s in g   t h ap p licatio n   o f   T r ie   d ata   s tr u ctu r i n   tex s ea r ch   b ased   o n   th e   p r e f ix   o f   th in p u tex t,   tr ain ed   u s in g   7 0 o f   th tr ai n in g   d ata  an d   test ed   with   3 0 o f   th test in g   d ata  f r o m   2 0 0   tex d ata  s cr ap ed .   C o m b in atio n   o f   L ev en s h tein   d is tan ce   alg o r ith m   an d   T r ie   ac h iev ed   an   ac c u r ac y   r ate  o f   8 2 . 2 5 with   an     F1   s co r o f   8 4 . 3 9 %.  T h is   te x co r r e ctio n   m o d el   p er f o r m e d   g o o d   tr an s latio n s   u s in g   B L E s co r with   a n   in cr ea s o f   1 . 5 5 % a f ter   te x t c o r r ec tio n   was p er f o r m e d .   T h is   r esear ch   ev alu ated   tex co r r ec tio n   u s in g   co m b in ati o n   o f   L ev e n s h tein   d is tan ce   an d   T r ie   alg o r ith m .   T h co m b in ati o n   u s ed   d ictio n ar y   o f   I n d o n esian   l an g u ag to   f in d   an d   co r r ec s p ellin g   er r o r   f o cu s ed   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J I n f   &   C o m m u n   T ec h n o l     I SS N:   2252 - 8 7 7 6       E va lu a tio n   o f te xt  co r r ec tio n   u s in g   a   co mb in a tio n   o L ev en s h tein   d is ta n ce   a n d   Tr ie   … ( C yn th ia   N a ta lie )   1349   in   lex ical  er r o r .   Su g g esti o n   f o r   f u r th er   r esear ch   u s in g   th c o m b in atio n   o f   L ev e n s h tein   d is tan ce   an d   T r ie   ca n   b co n d u cted   b y   ap p ly i n g   th i s   co m b in atio n   to   m u ltil an g u a g tex ts   with   s em an tic  lev el,   in clu d in g   b y   ad d in g   m o r tr ain in g   d ata  a n d   test   d at in   ter m s   o f   in c r ea s in g   th ac cu r ac y   v al u an d   F1   Sco r e.       ACK NO WL E DG E M E NT S   Au th o r   w o u ld   lik t o   th a n k   B in Nu s an tar a   Un iv er s ity   f o r   its   s u p p o r t   an d   r eso u r ce s   p r o v i d ed   th r o u g h o u t   th is   r esear ch .   Au th o r   also   ac k n o wled g Pro f .   Ab b Su g an d Gir s an g   f o r   h is   v a lu ab le  s u g g esti o n s   an d   g u id a n ce   th at   h elp e d   im p r o v e   th q u ality   o f   th is   r esear ch .   All  in d iv id u als  ac k n o wled g ed   h av p r o v id ed   co n s en t to   b e   m en tio n e d   in   th i s   s ec tio n .       F UNDING   I NF O R M A T I O N   T h is   r esea r ch   is   s u p p o r t e d   b y   t h e   f u n d i n g   f r o m   Di r e ct o r ate   o f   R es ea r c h ,   T ec h n o l o g y ,   an d   C o m m u n it y   Ser v i ce   o f   Mi n is t r y   o f   E d u ca ti o n ,   C u l t u r e,   R ese a r c h ,   a n d   T e c h n o lo g y   o f   th R ep u b li c   of   I n d o n esi a .       AUTHO CO NT RI B UT I O NS ST A T E M E N T   T h is   jo u r n al  u s es  th C o n tr ib u to r   R o les  T ax o n o m y   ( C R ed iT)   to   r ec o g n ize  in d iv id u al  au th o r   co n tr ib u tio n s ,   r ed u ce   au th o r s h ip   d is p u tes,  an d   f ac ilit ate  co llab o r atio n .     Na m o f   Aut ho r   C   M   So   Va   Fo   I   R   D   O   E   Vi   Su   P   Fu   C y n th ia  Nata lie                               Ab b Su g an d   Gir s an g                                 C     C o n c e p t u a l i z a t i o n   M     M e t h o d o l o g y   So     So f t w a r e   Va     Va l i d a t i o n   Fo     Fo r mal   a n a l y s i s   I     I n v e s t i g a t i o n   R     R e so u r c e s   D   :   D a t a   C u r a t i o n   O   :   W r i t i n g   -   O r i g i n a l   D r a f t   E   :   W r i t i n g   -   R e v i e w   &   E d i t i n g   Vi     Vi su a l i z a t i o n   Su     Su p e r v i s i o n   P     P r o j e c t   a d mi n i st r a t i o n   Fu     Fu n d i n g   a c q u i si t i o n         CO NF L I C T   O F   I N T E R E S T   ST A T E M E NT   Au th o r s   s tate  n o   co n f lict o f   in t er est.       I NF O RM E CO NS E N T   I n f o r m ed   co n s en t   was  n o t   ap p licab le  to   th is   r esear ch   b ec a u s n o   h u m an   p ar ticip a n ts   wer d ir ec tly   in v o lv ed .   T h is   r esear ch   u tili ze d   s ec o n d ar y   tex t u al  d at o b tain e d   f r o m   p u b licly   av ailab le  s o u r ce s ,     in clu d in g   an   I n d o n esian   lan g u ag d ictio n a r y   ac ce s s ed   th r o u g h   th k b b i - p y th o n   lib r ar y   an d   I n d o n esian     n ews te x t sam p les.       E T H I CAL AP P RO V AL   E th ical  ap p r o v al  was  n o r eq u ir ed   f o r   th is   r esear ch   b ec au s it  d id   n o in v o l v h u m a n   p ar ticip an ts ,   an im als,  o r   s en s itiv p er s o n al   d ata.   T h is   r esear c h   was  c o n d u cted   u s in g   s ec o n d a r y   tex tu al   d ata,   in clu d i n g   an   I n d o n esian   lan g u ag d ictio n ar y   ac ce s s ed   th r o u g h   t h k b b i - p y th o n   lib r a r y   an d   I n d o n esian   n ews  tex s am p les   f o r   tex t m i n in g   a n d   s p ellin g - c o r r ec tio n   e v alu atio n .       DATA AV AI L AB I L I T Y   T h d ata  s u p p o r ti n g   th e   f in d in g s   o f   t h is   r esear ch   co n s is o f   a n   I n d o n esian   lan g u ag d ictio n ar y   ac ce s s ed   th r o u g h   th k b b i - p y th o n   lib r ar y   an d   2 0 0   I n d o n esia n   n ews  tex s am p les  co n tain in g   b o th   co r r ec an d   m is s p elled   wo r d s ,   r an d o m l y   s am p led   f r o m   th I n d o n esia  New s   Data s et  av ailab le  o n   Kag g le   ( h ttp s :// www. k ag g le. co m /d ata s ets/ az izain u n n ajib /in d o n esia - n ews) .         Evaluation Warning : The document was created with Spire.PDF for Python.