Количество различий в строках

Обсуждение программ nnCron и nnCron LITE

Количество различий в строках

Postby Morituruz » Fri, 20 Dec 2013, 09:42

Как проще подсчитать количество различий в строках?
Как-то так:
Code: Select all
S" ABCDEFGH"
S" BBCDEFGI"
StringDiff .
2 Ok
User avatar
Morituruz
 
Posts: 727
Joined: Sun, 14 Oct 2007, 01:51

Re: Количество различий в строках

Postby VoidVolker » Fri, 20 Dec 2013, 10:31

Code: Select all
: StringDiff   \ ( a1 u2 a2 u2 -- n )
  { a1 u1 a2 u2 -- }
  u1 u2 MIN DUP IF
    u1 u2 - ABS   \ len n \ Стартовый счетчик - разница длины строк
    SWAP          \ n len
    a1 a2 ROT     \ n a1 a2 len
    0 DO
      OVER I + C@
      OVER I + C@       \ n a1 a2 c1 c2
      <> ABS            \ n a1 a2 ?
      >R ROT R> + -ROT
    LOOP
    2DROP
  THEN
;


Code: Select all
S" ABCDEFGH" S" BBCDEFGI" StringDiff .
2 Ok
95% вопросов уже обсуждались на форуме или ответы на них есть в мануале.        nnCron 1.93 b15.exe
Как правильно задавать вопросы.
User avatar
VoidVolker
Site Admin
 
Posts: 2898
Joined: Tue, 25 Apr 2006, 17:56

Re: Количество различий в строках

Postby Morituruz » Mon, 23 Dec 2013, 10:33

Спасибо.
Нашёл ещё такой алгоритм, но на больших строках он похоже неюзабельный, несколько минут ждал, так и не дождался:
Code: Select all
: levenshtein                          ( a1 n1 a2 n2 -- n3)
  DUP                                  \ IF either string is empty, dIFference
  IF                                   \ is inserting all CHARS from the other
    2>R DUP
    IF
      2DUP 1- CHARS + C@ 2R@ 1- CHARS + C@ =
      IF
        1- 2R> 1- RECURSE EXIT
      ELSE                             \ ELSE try:
        2DUP 1- 2R@ 1- RECURSE -ROT    \   changing first letter of s to t;
        2DUP    2R@ 1- RECURSE -ROT    \   remove first letter of s;
        1- 2R> RECURSE MIN MIN 1+      \   remove first letter of t,
      THEN                             \ any of which is 1 edit plus
    ELSE                               \ editing the rest of the strings
      2DROP 2R> NIP
    THEN
  ELSE
    2DROP NIP
  THEN
;
User avatar
Morituruz
 
Posts: 727
Joined: Sun, 14 Oct 2007, 01:51

Re: Количество различий в строках

Postby VoidVolker » Mon, 23 Dec 2013, 12:58

Пф, бред какой-то.
95% вопросов уже обсуждались на форуме или ответы на них есть в мануале.        nnCron 1.93 b15.exe
Как правильно задавать вопросы.
User avatar
VoidVolker
Site Admin
 
Posts: 2898
Joined: Tue, 25 Apr 2006, 17:56

Re: Количество различий в строках

Postby Morituruz » Mon, 23 Dec 2013, 13:12

Почему бред? На малых строчках прекрасно работает.
User avatar
Morituruz
 
Posts: 727
Joined: Sun, 14 Oct 2007, 01:51


Return to nnCron forum (Russian)

Who is online

Users browsing this forum: No registered users and 1 guest

cron