Что такое хорошая эвристика для определения ширины вкладки, используемой в исходном файле?
Я хотел бы определить ширину вкладки, используемой в исходных файлах с отступом. Это не сложно для файлов с особенно регулярным отступом, где начальные пробелы используются только для отступа, всегда в кратных ширине табуляции, а отступы увеличиваются на один уровень за раз. Но многие файлы будут иметь некоторые отклонения от такого рода регулярных отступов, как правило, для некоторой формы вертикального выравнивания. Поэтому я ищу хорошую эвристику, чтобы оценить, какая ширина вкладки была использована, что дает некоторую возможность для неправильного отступа.
Мотивация для этого - написание расширения для редактора 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
Рубин:
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, ограничивающая возможную ширину вкладки и проверяющая, часто ли встречается половина модального значения, с двумя различными пороговыми значениями для выбора меньшей ширины.
7 ответов
Ваш выбор (реально) 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)
- Для каждой строки в файле
- Если отступ больше предыдущего, добавьте разницу в список
- отменить, если> 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
Надеюсь, это поможет.
Хорошо, поскольку вы хотите решение, не зависящее от языка, мы не сможем использовать какие-либо синтаксические подсказки. Хотя вы сказали, что вам не нужно идеальное решение, вот одно, которое очень хорошо работает с большинством языков.
На самом деле мне пришлось решить аналогичную проблему в криптографии, чтобы получить правильную длину кодового слова в полиалфавитном шифре. Этот вид шифрования является базовым Caesar-chiffre (каждая буква алфавита перемещается на n букв), где криптографическое слово используется для перемещения букв по-разному (n-я буква открытого текста перемещается модом (nth, length). (cryptword)) буква криптового слова). Оружие выбора - автокорреляция.
Алгоритм будет выглядеть так:
- удалите все символы после пробела в начале строки - оставьте маркеры конца строки без изменений.
- удалить строки с нулевым пробелом (так как они являются только пустыми строками)
- Подсчитайте ширину пробелов для каждой строки и сохраните ее в массиве длины
- Автокорреляция: цикл до максимального оценочного числа - может быть достаточно высоким, как 32 или около того - текущая итерация должна быть i. Для каждой итерации вычислите расстояние между каждой записью и i-й записью. Подсчитать количество расстояний = 0 (одинаковые значения для n-й и (n+i) -й записей), сохранить в массиве для ключа i.
- Теперь у вас есть массив одинаковых парных происшествий. Вычислите среднее значение этого массива и удалите все значения, близкие к этому среднему (оставляя пики автокорреляции). Пики будут кратны минимальному значению, которое будет искомым числом пробелов, используемых для отступа.
Автокорреляция - это очень хорошая функция, которую можно использовать в любой ситуации, в которой вы хотите обнаружить повторяющиеся значения в потоке данных. Он интенсивно используется при обработке сигналов и очень быстрый (в зависимости от расчетного максимального расстояния повторений сигнала).
И да, тогда я взломал полиалфавитный шифротекст с автокорреляцией.;)
Может быть, сделать что-то вроде...
- получить список всех значений ширины вкладки в файле
- удалить 50% записей, которые являются наименее частыми
- отсортировать оставшиеся записи в порядке возрастания
- вычислить список пар (a, b), где b находятся в списке ширины вкладок, а a дают ранг этой ширины вкладок.
- построить наиболее подходящую линию
- наклон линии наилучшего соответствия - это предположение о ширине вкладки. округлить до ближайшего целого числа.
Пример:
- list = [4, 4, 6, 8, 8, 4, 4, 4, 8, 8, 12, 5, 11, 13, 12, 12]
- список = [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, так что это, вероятно, ширина вкладки.
Для каждого языка, который вы хотите поддерживать, вам нужно немного разобрать:
1) исключить комментарии (построчные или блочные, может быть и вложенные?)
2) найти отверстия подблока ({ на C-подобных языках, begin в паскале, do в оболочке и т. д.)
Тогда просто посмотрите, насколько увеличится количество пробелов после того, как субблок был открыт. Сделайте несколько простых статистических данных - чтобы найти наиболее частое значение, максимальное и минимальное значение, среднее значение. Таким образом, вы также можете увидеть, является ли отступ регулярным или нет и сколько.
Эвристический:
- Получить список всех изменений отступа от строки до следующей строки, которые> 0.
- Составьте таблицу частот всех значений в этом списке.
- Возьмите значение с максимальной частотой.
Скрипт Python, принимает имена файлов или стандартный ввод и печатает лучший номер отступа:
#!/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()))
В качестве базовой линии можно просто рассчитать все увеличения отступов и принять наиболее частое увеличение в качестве ширины вкладки. Как сценарий оболочки, написанный для небольших действий на стадии конвейера, он может выглядеть так:
#!/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),