0

假设我有一些文本（代码）：

  def text = ParamMenuable.this.linkText
  def locPath: List[LocPath] = ParamMenuable.this.path
  def parser = ParamMenuable.this.parser
  def listToFrom(in: List[String]): Box[String] = in.headOption

还有一些快捷键：

arrow-left/right/up/down:  move cursor to left/right/up/down for one char

ctrl + d: duplicate current line
ctrl + arrow-left/right/up/down:  move cursor to left/right/up/down for one word
ctrl + y: delete current line
... all kinds of key shorts you usually used

目标文本是：

  def text() = {
     ParamMenuable.this.linkText
  }
  def locPath: List[LocPath] = ParamMenuable.this.path
  def locPath22222: List[LocPath] = ParamMenuable.this.path
  private def parser = {
      return ParamMenuable.this.parser;
  }

我的问题是：您至少应该按下多少键才能将源文本转换为目标？您可以选择合适的钥匙短裤来做得更好。

4

2 回答 2

2

这可能是NP难的。本文为编辑器提供了一个硬度证明，其中插入、删除和子字符串移动都具有恒定成本。

%0 Book Section
%D 2002
%@ 978-3-540-43862-5
%B Combinatorial Pattern Matching
%V 2373
%S Lecture Notes in Computer Science
%E Apostolico, Alberto
%E Takeda, Masayuki
%R 10.1007/3-540-45452-7_9
%T Edit Distance with Move Operations
%U http://dx.doi.org/10.1007/3-540-45452-7_9
%I Springer Berlin Heidelberg
%8 2002-01-01
%A Shapira, Dana
%A Storer, JamesA.
%P 85-98
%G English
于 2013-07-17T12:26:30.730 回答
0

接近的东西是http://en.wikipedia.org/wiki/Levenshtein_distance

不过，它仅适用于字符串，不适用于填充文本的二维区域。

但是，以下应该是可能的：

possible
postibla

在这里，Levenshtein 距离应该是 2（因为必须更改 2 个字符才能将“可能”变为“postibla”），但也应该可以打印一个必须执行更改的跟踪，例如：

change 's' on position 4 to 't'
change 'e' on position 8 to 'a'

并且，反过来，将其更改为一系列光标移动等（假设光标在最左边）：

-> -> -> DEL 't' -> -> -> DEL $ 'a'

（这里，符号$表示光标位于行尾的事实。）然后我们可以应用优化规则，例如：

(->)+$     =>   END
(->)+DEL$  =>   END BS

等等。

只是想法....

于 2013-07-17T12:49:39.157 回答