12

スペースでインデントされたソース ファイルで使用されるタブ幅を特定したいと考えています。これは、先頭のスペースがインデントにのみ使用され、常にタブ幅の倍数であり、インデントが一度に 1 レベルずつ増加する、特に規則的なインデントを持つファイルでは難しくありません。しかし、多くのファイルは、通常、何らかの形式の垂直方向の配置のために、この種の通常のインデントとは多少異なります。したがって、不規則なインデントの可能性を考慮して、使用されたタブ幅を推定するための優れたヒューリスティックを探しています。

これの動機は、SubEthaEdit エディターの拡張機能を作成することです。残念ながら、SubEthaEdit ではタブ幅をスクリプトで使用できないため、テキストに基づいて推測します。

適切なヒューリスティックは次のようにする必要があります。

  • インタラクティブな使用に十分なパフォーマンス。これが問題になるとは思いません。必要に応じて、テキストの一部だけを使用できます。
  • 言語に依存しない。
  • 適切な最長のタブ幅を返します。たとえば、タブ幅が 4 スペースのファイルは、すべてのインデントが実際には 2 倍のレベルである場合、2 スペース タブのファイルである可能性もあります。明らかに、4 つのスペースが正しい選択です。
  • インデントが完全に規則的である場合は、常に正しくします。

いくつかの単純化要因:

  • 少なくとも 1 行はインデントされていると見なすことができます。
  • タブの幅は、少なくとも 2 つのスペースであると見なすことができます。
  • インデントはスペースのみで行われると想定しても安全です。タブに反対しているわけではありません---逆に、インデントに使用されているタブがあるかどうかを最初に確認し、個別に処理します。これは、タブとスペースが混在するインデントが適切に処理されない可能性があることを意味しますが、重要ではないと考えています。
  • 空白のみを含む行はないと考えられます。
  • すべての言語を正しく処理する必要があるわけではありません。たとえば、lisp や go などの言語では、通常は手作業でインデントを行うことはないため、成功または失敗はまったく関係ありません。
  • 完璧は必要ありません。数行を手動で調整する必要がある場合でも、世界が終わることはありません。

どのようなアプローチを採用し、その長所と短所は何だと思いますか?

回答で動作するコードを提供したい場合、最善の方法はおそらく、ソース ファイルを から読み取り、stdinタブ幅を に書き込むシェル スクリプトを使用することstdoutです。擬似コードまたは言葉による明確な説明でも問題ありません。

いくつかの結果

さまざまな戦略をテストするために、言語ディストリビューションの標準ライブラリ内のファイルにさまざまな戦略を適用できます。おそらく、言語の標準的なインデントに従っているからです。Python 2.7 ライブラリと Ruby 1.8 ライブラリ (システム フレームワークは Mac OS X 10.7 にインストールされます) を検討します。これらのライブラリのタブ幅は、それぞれ 4 と 2 であると予想されます。タブ文字で始まる行があるファイル、または少なくとも 2 つのスペースで始まる行がないファイルは除外されます。

パイソン:

                     Right  None  Wrong
Mode:                 2523     1    102
First:                2169     1    456
No-long (12):         2529     9     88
No-long (8):          2535    16     75
LR (changes):         2509     1    116
LR (indent):          1533     1   1092
Doublecheck (10):     2480    15    130
Doublecheck (20):     2509    15    101

ルビー:

                     Right  None  Wrong
Mode:                  594    29     51
First:                 578     0     54
No-long (12):          595    29     50
No-long (8):           597    29     48
LR (changes):          585     0     47
LR (indent):           496     0    136
Doublecheck (10):      610     0     22
Doublecheck (20):      609     0     23

これらの表で、「正しい」は言語標準のタブ幅の決定、「正しくない」は言語標準の幅と等しくないゼロ以外のタブ幅、「なし」はタブ幅がゼロまたはないものとして解釈する必要があります。答え。「モード」は、インデントで最も頻繁に発生する変更を選択する戦略です。「最初」は、最初のインデントされた行のインデントを取ります。"No-long" は、大きなインデントのある行を除外してモードを取る FastAl の戦略であり、数字はインデントの最大許容変更を示します。「LR」は、線形回帰に基づく Patrick87 の戦略であり、行間のインデントの変化と行の絶対インデントに基づくバリアントがあります。"Doublecheck" (だじゃれに抵抗できなかった!) は、FastAl の Mark の修正です。

4

7 に答える 7

3

言語にとらわれないソリューションが必要なため、構文上のヒントは使用できません。あなたは完璧な解決策を望まないと言いましたが、ほとんどの言語で非常にうまく機能している解決策があります。

多アルファベット暗号で正しいコードワード長を取得するには、実際に暗号化で同様の問題を解決する必要がありました。この種の暗号化は、基本的な Caesar-chiffre (アルファベットの各文字がn文字ずつ移動する) であり、暗号語を使用して文字を異なる方法で移動します (クリア テキストの n 番目の文字はmod (nth, length (暗号語)) 暗号語の文字)。最適な武器は自己相関です。

アルゴリズムは次のようになります。

  1. 行頭の空白が終了した後のすべての文字を削除します。行末マーカーはそのまま残します。
  2. 空白がゼロの行を削除します（空白行のみであるため）
  3. 各行の空白の幅を数え、これを長さの配列に保存します
  4. 自己相関: 最大推定数までループします - 32 か何かのようにかなり高いかもしれません - 現在の反復はiになります。反復ごとに、各エントリとi 番目のエントリの間の距離を計算します。距離の数 = 0 (n 番目と (n+i) 番目のエントリは同じ値) をカウントし、キーiの配列に保存します。
  5. これで、同じペアの出現の配列ができました。この配列の平均を計算し、この平均に近いすべての値を削除します (自己相関のスパイクを残します)。スパイクは、インデントに使用されるスペースの検索数である最低値の倍数になります。

自己相関は非常に優れた関数であり、データ ストリーム内の繰り返し値を検出するあらゆる状況で使用できます。これは、信号処理で頻繁に使用され、非常に高速です (信号反復の推定最大距離によって異なります)。

そうです、当時、私は多アルファベット暗号文を自己相関で解読しました。;)

于 2011-08-23T14:13:25.570 に答える
2
  • ファイルの各行について
    • 以前よりもインデントされている場合は、違いをリストに追加します
      • > 12の場合は破棄します、おそらく行の継続です
  • リスト内の＃の度数分布表を生成します
  • ＃1はおそらくあなたの答えです。

編集

私はVB.Netを開いています（そうではありませんか？:-)これが私が意味することです：

    Sub Main()
        Dim lines = IO.File.ReadAllLines("ProveGodExists.c")
        Dim previndent As Integer = 0
        Dim indent As Integer
        Dim diff As Integer
        Dim Diffs As New Dictionary(Of Integer, Integer)
        For Each line In lines
            previndent = indent
            indent = Len(line) - Len(LTrim(line))
            diff = indent - previndent
            If diff > 0 And diff < 13 Then
                If Diffs.ContainsKey(diff) Then
                    Diffs(diff) += 1
                Else
                    Diffs.Add(diff, 1)
                End If
            End If
        Next
        Dim freqtbl = From p In Diffs Order By p.Value Descending
        Console.WriteLine("Dump of frequency table:")
        For Each item In freqtbl
            Console.WriteLine(item.Key.ToString & " " & item.Value.ToString)
        Next
        Console.WriteLine("My wild guess at tab setting: " & freqtbl(0).Key.ToString)
        Console.ReadLine()
    End Sub

結果：

度数分布表のダンプ：
4 748
8 22
12 12
2 2
9 2
3 1
6 1
タブ設定での私のワイルドな推測：4

お役に立てば幸いです。

于 2011-08-18T20:41:01.023 に答える
1

あなたの選択は（現実的に）2、3、4、5、6、7、8です。

@FastAlが提案したようなものを使用して、最初の50〜100行程度をスキャンします。私はおそらく、テキストのある行の前からスペースカウントを盲目的に引っ張って、空白文字列の長さをカウントすることに傾倒するでしょう。正規表現を使用できる場合、左のトリミングラインと2回のランニングレングスは無駄に思えます。また、私はSystem.Math.abs(indent - previndent)あなたがデータのインデントを解除するようにします。正規表現は次のようになります。

row.matches('^( +)[^ ]') # grab all the spaces from line start to non-space.

7つのオプションのどれが最もカウントが高いかについての統計を取得したら、それを最初の推測として実行します。8、6、および4の場合、4および2、3、または2の有意なカウント（2位または10％以上、またはその他の安価なヒューリスティック）があるかどうかを確認する必要があります。または9s）は、4（または3）が8（または6）よりも優れた選択であることを示唆している可能性があります。一度に2つ以上のレベル（通常は折りたたまれた終了ブラケット）を削除または追加することは非常にまれです。

無関係なつぶやき

私が見ている問題の1つは、特に古い.cコードで、この厄介なパターンが発生していることです。

code level 0
/* Fancy comments get weird spacing because there 
 * is an extra space beyond the *
 * looks like one space!
 */
  code indent (2 spaces)
  /* Fancy comments get weird spacing because there 
   * is an extra space beyond the *
   * looks like three spaces!
   */

code level 0
  code indent (2 spaces)
  /* comment at indent level 1
     With no stars you wind up with 2 spaces + 3 spaces.
  */

うん。あなたがそのようなコメント基準をどのように扱っているのか分かりません。バージョン2.0で特別なコメントを処理する必要があるような「c」のコードの場合...しかし、今のところは無視します。

あなたの最後の問題はあなたの仮定と一致しない行を扱うことです。私の提案は、それらを深さまで「タブ」してから、余分なスペースをそのままにしておくことです。あなたが修正しなければならないなら、私はこれをします：rowtabdepth = ceiling((rowspacecount - (tabwidth/2)) / tabwidth)

于 2011-08-24T19:01:11.057 に答える
1

たぶん、次のようなことをします...

  1. ファイル内のすべてのタブ幅のリストを取得します
  2. 最も頻度の低いエントリの 50% を削除します
  3. 残りのエントリを昇順に並べ替える
  4. (a, b) ペアのリストを計算します。ここで、b はタブ幅のリストにあり、a はそのタブ幅のランクを示します。
  5. 最適な線をプロットする
  6. 最適な線の傾きは、タブ幅の推測です。最も近い整数に丸めます。

例：

  1. リスト = [4, 4, 6, 8, 8, 4, 4, 4, 8, 8, 12, 5, 11, 13, 12, 12]
  2. リスト = [4、4、4、4、4、8、8、8]
  3. ソート済み
  4. [(1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (2, 8), (2, 8), (2, 8)]
  5. 最適な直線は b = 4a + 0 (R^2 = 0) です
  6. スロープは 4 なので、これはおそらくタブ幅です。
于 2011-08-09T16:31:52.433 に答える
0

ヒューリスティック：

  1. 行から次の行までのすべてのインデント変更のリストを取得します。これは > 0 です。
  2. このリストのすべての値の頻度表を作成します。
  3. 頻度が最も高い値を取ります。

Python スクリプトは、ファイル名または stdin を受け取り、最適なインデント番号を出力します。

#!/usr/bin/env python

import fileinput, collections

def leadingSpaceLen(line):
    return len(line) - len(line.lstrip())

def indentChange(line1, line2):
    return leadingSpaceLen(line2) - leadingSpaceLen(line1)

def indentChanges(lines):
    return [indentChange(line1, line2)
        for line1, line2 in zip(lines[:-1], lines[1:])]

def bestIndent(lines):
    f = collections.defaultdict(lambda: 0)
    for change in indentChanges(lines):
        if change > 0:
            f[change] += 1
    return max(f.items(), key=lambda x: x[1])[0]

if __name__ == '__main__':
    print bestIndent(tuple(fileinput.input()))
于 2011-08-24T14:29:38.163 に答える
0

ベースラインとして、すべてのインデントの増加を単純に計算し、最も頻繁に増加するものをタブ幅として使用できます。パイプライン ステージごとに小さなアクションを持つように記述されたシェル スクリプトとしては、次のようになります。

#!/bin/sh

grep -v -E '^[[:space:]]*$' | 
  sed 's/^\([[:space:]]*\).*/\1/' | 
    awk '{ print length($0) }' | 
      awk '$1 > prev { print $1 - prev } { prev = $1 }' | 
        sort | 
          uniq -c | 
            sort -k1nr | 
              awk '{ print $2 }' | 
                head -n 1

この実装はファイル内の行数ですO(n log(n))がn、 で簡単に実行できますO(n)。

于 2011-08-17T18:18:16.957 に答える
0

サポートしたい言語ごとに、少し解析を行う必要があり ます
。言語、パスカル、シェルなど)
{begindo

次に、サブブロックが開かれた後にスペースの数がどれだけ増加するかを確認してください。いくつかの簡単な統計を作成します - 最も頻繁な値、最大値と最小値、平均値を見つけます。このようにして、インデントが規則的かどうか、およびその程度も確認できます。

于 2011-08-09T14:33:00.820 に答える