Что такое хорошая эвристика для определения ширины вкладки, используемой в исходном файле?

Question

Я хотел бы определить ширину табуляции, используемую в исходных файлах с отступом.Это не сложно для файлов с особенно регулярным отступом, где начальные пробелы используются только для отступа, всегда в кратных ширине табуляции, а отступы увеличиваются на один уровень за раз.Но многие файлы будут иметь некоторые отклонения от такого рода регулярных отступов, как правило, для некоторой формы вертикального выравнивания.Поэтому я ищу хорошую эвристику, чтобы оценить, какая ширина вкладки была использована, что дает некоторую возможность для неправильного отступа.

Мотивация для этого - написать расширение для редактора SubEthaEdit.К сожалению, SubEthaEdit не делает ширину вкладки доступной для сценариев, поэтому я собираюсь угадать ее на основе текста.

Подходящая эвристика должна:

• Работать достаточно хорошо для интерактивного использования.Я не думаю, что это будет проблемой, и только часть текста может быть использована в случае необходимости.
• Быть независимым от языка.
• Возвращает самую длинную подходящую ширину вкладки.Например, любой файл с шириной табуляции в четыре пробела также может быть файлом с табуляцией в два пробела, если каждый отступ на самом деле вдвое больше уровней.Ясно, что четыре пробела были бы правильным выбором.
• Всегда делайте все правильно, если отступы полностью правильные.

Некоторые упрощающие факторы:

• Можно предположить, что отступ по крайней мере для одной строки.
• Можно предположить, что ширина вкладки равна по крайней мере двумпространства.
• Можно предположить, что отступ выполняется только с пробелами.Дело не в том, что я имею что-то против вкладок - наоборот, сначала я проверю, есть ли вкладки для отступов, и обработаю их отдельно.Это означает, что вкладки и пробелы смешивания отступов могут обрабатываться неправильно, но я не считаю это важным.
• Можно предположить, что нет строк, содержащих только пробелы.
• Не все языки должны обрабатываться правильно.Например, успех или неудача с такими языками, как lisp и go, были бы совершенно не важны, поскольку они обычно не имеют отступов вручную.
• Совершенство не требуется.Мир не закончится, если несколько строк иногда придется настраивать вручную.

Какой подход вы бы выбрали, и в чем вы видите его преимущества и недостатки?

Если вы хотите предоставить рабочий код в своем ответе, лучшим подходом, вероятно, является использованиесценарий оболочки, который читает исходный файл из stdin и записывает ширину вкладки в stdout.Псевдокод или четкое описание на словах тоже подойдет.

Некоторые результаты

Чтобы протестировать разные стратегии, мы можем применять разные стратегии к файлам в стандартных библиотеках для языковых дистрибутивов, так как они предположительно следуют стандартному отступу для языка,Я рассмотрю библиотеки Python 2.7 и Ruby 1.8 (системная среда устанавливается на Mac OS X 10.7), которые ожидают ширину вкладок 4 и 2 соответственно.Исключаются те файлы, у которых есть строки, начинающиеся с символов табуляции или у которых нет строк, начинающихся как минимум с двух пробелов.

Python:

                     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

Ruby:

                     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

В этих таблицах «Право» следует принимать как определение ширины языковой стандартной закладки, «Неверно» - ненулевую ширину вкладки, не равную стандартной языковой ширине, и «Нет» - нулевую вкладку. ширина или нет ответа. «Режим» - это стратегия выбора наиболее часто встречающегося изменения отступа; «First» принимает отступ первой строки с отступом; «No-long» - это стратегия FastAl по исключению строк с большим отступом и переходу в режим, где число указывает максимально допустимое изменение отступа; «LR» - это стратегия Patrick87, основанная на линейной регрессии, с вариантами, основанными на изменении отступа между строками и абсолютном отступе строк; «Двойная проверка» (не смог противостоять каламбуру!) - это модификация Марка стратегии FastAl, ограничивающая возможную ширину вкладки и проверяющая, часто ли встречается половина модального значения, с двумя различными порогами для выбора меньшей ширины.

Answer 1

Хорошо, поскольку вы хотите решение, не зависящее от языка, мы не сможем использовать какие-либо синтаксические подсказки.Хотя вы сказали, что вам не нужно идеальное решение, вот одно, которое очень хорошо работает с большинством языков.

Мне действительно пришлось решить аналогичную проблему в криптографии, чтобы получить правильную длину кодового словав полиалфавитном шифре .Этот вид шифрования является основным Цезарь-шиффра (каждая буква алфавита перемещается на n букв), где криптографическое слово используется для перемещения букв по-разному ( nth буквачистый текст перемещается с помощью мода (nth, length (cryptword)) буква cryptword).Оружие выбора - автокорреляция .

Алгоритм будет выглядеть следующим образом:

1. убрать все символы после пробела в начале строки -оставьте маркеры конца строки без изменений.
2. удалите строки с нулевым пробелом (поскольку они являются только пустыми строками)
3. Подсчитайте ширину пробела для каждой строки и сохраните ее в массиве длины
4. Автокорреляция : цикл до максимального расчетного числа - может быть достаточно высоким, как 32 или около того - текущая итерация должна быть i .Для каждой итерации вычислите расстояние между каждой записью и записью ith .Посчитайте количество расстояний = 0 (те же значения для nth и (n + i) th записей), сохраните в массив для ключа i .
5. Теперь у вас есть массив совпадений одинаковых пар.Вычислите среднее значение этого массива и удалите все значения, близкие к этому среднему (оставляя пики автокорреляции).Пики будут кратны наименьшему значению, которое будет искомым числом пробелов, используемых для отступа.

Автокорреляция - это очень хорошая функция, которую можно использовать для любой ситуации, в которой вы хотите обнаружитьповторяющиеся значения в потоке данных.Он интенсивно используется при обработке сигналов и очень быстрый (в зависимости от предполагаемого максимального расстояния повторений сигнала).

И да, тогда я взломал полиалфавитный шифротекст с автокорреляцией.;)

Answer 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 * ​​1027 * 12 12
2 2
9 2
3 1
6 1
Моя дикая догадка при установке вкладок: 4

Надеюсь, это поможет.

Answer 3

Ваш выбор (реально) 2,3,4,5,6,7,8.

Я бы просканировал первые 50-100 строк или около того, используя что-то вроде того, что предложил @FastAl. Вероятно, я бы склонялся к тому, чтобы просто вслепую вытянуть количество пробелов с начала любого ряда с текстом и посчитать длину строки пробела. Левые линии обрезки и длина бега в два раза кажутся пустой тратой, если у вас есть регулярное выражение Кроме того, я бы сделал System.Math.abs(indent - previndent), чтобы вы получили данные отступа. Регулярное выражение будет следующим:

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

Как только вы получите статистику, для которой из 7 вариантов есть наибольшее количество, запустите ее в качестве первого предположения. Для 8, 6 и 4 вы должны проверить, есть ли также значительный счет (2-е место или более 10% или некоторый другой дешевый эвристический анализ) для 4 и 2, 3 или 2. Если есть много 12 ( или 9s), что может указывать на то, что 4 (или 3) - лучший выбор, чем 8 (или 6). Пропуск или добавление более 2-х уровней за раз (обычно свернутые конечные скобки) встречается очень редко.

Неуместное бормотание

Единственная проблема, которую я вижу, заключается в том, что в старом .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.
  */

Тьфу. Я не знаю, как вы справляетесь с такими стандартами комментариев. Для кода, который "c", как вы, возможно, придется иметь дело с комментариями, специально для версии 2.0 ... но я бы просто проигнорировал это на данный момент.

Ваша последняя проблема связана со строками, которые не соответствуют вашим предположениям. Мое предложение было бы «уложить» их на глубину, а затем оставить дополнительные места на месте. Если вам нужно исправить, я сделаю это: rowtabdepth = ceiling((rowspacecount - (tabwidth/2)) / tabwidth)

Answer 4

Может быть сделать что-то вроде ...

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. list = [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, так что это, вероятно, ширина вкладки.

Answer 5

Для каждого языка, который вы хотите поддерживать, вам нужно выполнить небольшой синтаксический анализ:
1) исключить комментарии (по строкам или по блокам, возможно, также вложенные?)
2) найтиоткрытия субблока ({ на C-подобных языках, begin на паскале, do в оболочке и т.был открыт.Сделайте несколько простых статистических данных - чтобы найти наиболее частое значение, максимальное и минимальное значение, среднее значение.Таким образом, вы также можете увидеть, является ли отступ регулярным или нет и сколько.

Answer 6

Эвристический:

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()))

Answer 7

В качестве базовой линии можно просто рассчитать все увеличения отступов и принять наиболее частое увеличение в качестве ширины вкладки. Как сценарий оболочки, написанный для небольших действий на стадии конвейера, он может выглядеть так:

#!/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).