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

Ответ 1

Ваш выбор (реалистично) 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). Сбрасывание или добавление более двух уровней за раз (обычно сложенные скобки) очень редко.

Небрежное бормотание

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

Ответ 2

• Для каждой строки в файле
  • Если с отступом больше предыдущего, добавьте разницу в список
    • отменить if > 12, это, вероятно, продолжение строки
• Создайте частотную таблицу #s в списке
• # 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

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

Ответ 3

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

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

Алгоритм будет таким:

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

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

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

Ответ 4

Может быть, что-то вроде...

• получить список всех ширины табуляции в файле
• удалить 50% наименее часто используемых записей
• сортировать остальные записи в порядке возрастания
• вычислить список (a, b) пар, где b находится в списке ширины табуляции, а a дать ранг этой ширины табуляции.
• построить линию наилучшего соответствия
• Наклон линии наилучшего соответствия - это предположение о ширине табуляции. округлить до ближайшего целого числа.

Пример:

• list = [4, 4, 6, 8, 8, 4, 4, 4, 8, 8, 12, 5, 11, 13, 12, 12]
• list = [4, 4, 4, 4, 4, 8, 8, 8]
• уже отсортировано
• [(1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (2, 8), (2, 8), (2, 8 )]
• лучшая линия соответствия - это b = 4a + 0 (R ^ 2 = 0)
• Наклон равен 4, так что это, вероятно, ширина табуляции.

Ответ 5

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

Затем просто посмотрите, сколько увеличивается количество пробелов после открытия подблока. Сделайте несколько простых статистических данных - чтобы найти наиболее частое значение, максимальное и минимальное значение, среднее значение. Таким образом вы также можете увидеть, является ли отступы регулярными или нет и сколько.

Ответ 6

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

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

Ответ 7

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

• Получить список всех изменений отступа от строки до следующей строки, которая равнa > 0.
• Сделать таблицу частот всех значений в этом списке.
• Возьмите значение с максимальной частотой.

Python script, принимает имена файлов или 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()))