Распознавание строк

[jangle]

Как бы проще решить задачау распознавания строк, допустим есть адрес записанный несколькими способами

Жилой дом 24 этажа улица Яблочкова дом 7 квартира 7
ул. Яблочкова д.7 кв.7
Дом жилой Яблочкова7 к. 7
Жилой дом ул ЯБЛОЧКОВА КВ 7 ДОМ 7

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

[Денис]

К сожалению, в общем случае никак. Я раньше решал такую задачу в два шага:
1. Последовательными заменами привожу список к некоему общему стандарту: например, заменяем "кв ", "квартира " и т.п. на "кв. "
2. Пытаемся парсить преобразованный массив.
Если ш.2 не получается, возвращаемся к ш.1. Рекурсивно.
Даже не владея регэкспами, я приводил к удобочитаемому виду базу адресов, набивавшуюся несколькими поколениями планктона, причем каждое поколение страдало своими грамматическими изъянами. И при этом всём, вручную доводить приходилось адресов 10-20 из полторы тысячи.

[jangle]

К сожалению, в общем случае никак. Я раньше решал такую задачу в два шага:
1. Последовательными заменами привожу список к некоему общему стандарту: например, заменяем "кв ", "[b]

Мне кажется эта идея здравой. Приводить строки к промежуточному стандарту:

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

[Хакер]

Баян же. Амед уже спрашивал подобное. К чему тогда пришли?

[jangle]

Баян же. Амед уже спрашивал подобное. К чему тогда пришли?

К чему пришли?

[Roman Koff]

ИИ на НС

[jangle]

ИИ на НС

Мне что ИИ прийдется разработать?

[Roman Koff]

Нет, чтобы тебе разобрать именно эти стройки, то конечно не прийдется, а в общем смысле да, и потом еще потратить время на обучение системы.

[qwertyhp]

Не понял: речь идёт об оптическом распознавании или же о логическом? Если о логическом: Сначала с номерами домов и т.п. Номер - это числа, а не буквы: делаем парсинг строки, и если ты не IsNumeric - то автоматически превращаешься в пробел. Получаем строку с несколькими числами, разделёнными кучками пробелов. Длина новой строки равна длине исходной, позиции чисел в обеих строках также одинаковы.
Далее.
Номеру дома предшествует название улицы.
Если адреса в пределах одного города - взять список улиц города (по Москве есть, могу выложить). И парсить ИСХОДНУЮ строку СПРАВА-НАЛЕВО на предмет поиска совпадения с названием улицы из списка улиц города. Предварительно всё перевести в один регистр, а транслит типа "a"="а" организовать несложно.
Вот, нашли совпадение: Яблочкова. Теперь все группки цифр, что правее совпадения - это будут дом, корпус (опционально), квартира. Из них дом самый левый, квартира самая правая. В НОВОЙ строке их разделяют только пробелы, позиции других (не пробелов) знаков в строке такие же, как в оригинале: поэтому
ДомКорпусКвартира = Mid$(НОВАЯ строка, [от позиции левее слова Яблочкова]).
ДомКорпусКвартира разделены пробелами. Дом = InStr(ДомКорпусКвартира, " "), и Квартира = InStrRev(ДомКорпусКвартира, " "). То, что посередине - это корпус.

Некоторая сложность в том, что могут быть "1-я улица строителей", "2-я улица строителей", "3-я улица строителей" (я совершенно серьёзно), - которые, к тому же, могут быть записаны как "улица строителей 1-я", "улица строителей 2-я", и т.д. - что, кстати, тоже грамотно. Но в этом случае почти гарантированно присутствие "хвостика" "-я", который и укажет, что число относится всё-таки к названию улицы, а не номеру дома.
Если же нужно оптическое распознавание (с рисунка) - то алгоритм сейчас разрабатывается. Правда, только для шрифтов, подобных "Areal". А попутно вопрос: как цветной рисунок программно сделать чёрно-белым (не монохромным, а именно - чёрно-белым)? Пока пользуюсь сторонним графическим редактором, но в ОСР это ведь не прокатит...
jangle, спасибо за архиватор.

[Debugger]

Номеру дома предшествует название улицы.

Вот облом: юзеры могут написать наоборот/записать кроме всего другие числа (например, номер этажа)/вообще не записать какую-то часть данных.

[Roman Koff]

Если же нужно оптическое распознавание (с рисунка) - то алгоритм сейчас разрабатывается. Правда, только для шрифтов, подобных "Areal".

В нетленку - адназначно ж)))))))))))))))

[jangle]

Если адреса в пределах одного города - взять список улиц города (по Москве есть, могу выложить)

Если это отформатированный список в TXT файле, пожалуйста выложи. И список любых объектов по Москве если есть, ТЭЦ, АТС, заводы и т.д.

[qwertyhp]

Список улиц Москвы выкладываю в архиве. Других объектов нет, но посмотрю в Сети.

2Roman Koff: "...для шрифтов, подобных "Areal". Странно, что вас, вероятно, не удивляет - как это Microsoft сразу не выпустила Windows XP для IBM XT, а начала с Windows 1.0? Вот точно также и в других случаях. От простого - к сложному. От частного - к общему. Если можете предложить алгоритм на уровне, достаточном для перевода в код - предлагайте. А суждения вида "ИИ на НС" - это правильно, а пользы? Человеку нужно решить конкретно задачу. К тому же, подозреваю, что одновременно однотипные задачи решают более одного форумчанина. Поэтому - по-существу. Лучше подскажите - как цветной рисунок программно сделать чёрно-белым (не монохромным, а именно - чёрно-белым)? Опять же - это промежуточная задача, конечная - написать эффективную ОСР.
2Debugger: могут. Юзеры - они такие. Но по-любому, у каждого изврата есть свой логический предел, после которого он просто перестаёт распознаваться. Давайте посмотрим, что мы имеем: название улиц(ы) - с учётом транслита и возможных грамматических ошибок; номера домов и т.п.: последовательность чисел может быть любая, но она должна распознаваться. Например, запись "Расковой 5-1-77" как московский адрес интерпретируется как УЛИЦА+ДОМ+КОРПУС+КВАРТИРА. Если кто-то считает, что это УЛИЦА+ПОДЪЕЗД+ЭТАЖ+код домофона - пусть напишет.
После того, как мы локализовали числа (писал ранее), можно пощупать пространство слева и справа от них. Числу может предшествовать признак адреса - например, слово "дом". Или одна буква "д". Конечно, может быть и запись вида "1-2-3" - и пояснение "корпус, квартира, дом" - но это уже клиника.
Итак, слева и справа от чисел ищем ближайшие слова и смотрим первые буквы. Если "д 7" - это дом. Если "к 5" - это квартира, если "к" одна, и КОРПУС + Квартира, если имеем запись вида " к 5 к 9". В общем случае, следует предусмотреть все формы записи, за пределами которых запись просто перестаёт быть правильной. Например, если пропущена квартира. Да, это ИИ. И подозреваю, что простое решение придёт после неоднократных попыток наиболее полно решить задачу "в лоб".

[alex77755]

Как-то попадался пример

Код: Выделить всё

'Эта пример конвертирует цветную картинку в черно-белую с коэффицентами принятыми в телевидении.
'На форме необходимо разместить кнопку и 2 PictureBox с именами pic1 и pic2 одинакового размера. Свойство ScaleMode у обоих надо выставить в 3-Pixel. В pic1 загрузите любое изображение и нажмите на кнопку.

Private Sub Command1_Click()
Dim B1 As Byte, B2 As Byte, b3 As Byte
Dim lColor&, x&, y&, Gray
Dim Gra
pic2.Cls
For x = 0 To pic1.ScaleWidth
For y = 0 To pic1.ScaleHeight
lColor = pic1.Point(x, y)
B1 = lColor And &HFF 'Красный
B2 = (lColor \ 256) And &HFF 'Зеленый
b3 = (lColor \ 65536) And &HFF 'Синий

Gray = B1 * 0.3 + B2 * 0.59 + b3 * 0.11
lColor = RGB(Gray, Gray, Gray)
pic2.PSet (x, y), lColor

Next y
DoEvents
Next x
End Sub

[qwertyhp]

2 alex77755: спасибо, всё работает!

[qwertyhp]

Вот транслит плюс ошибки набора:

Код: Выделить всё

Select Case Tmp ' буква, возникшая в результате парсинга строки
' Tmp1 [2],[3]  ' различные варианты прочтения латинского символа как кириллического
    Case "a"
        Tmp1 = "а"
    Case "b"
        Tmp1 = "б"
        Tmp2 = "в"
        Tmp3 = "6"
    Case "c"
        Tmp1 = "с"
        Tmp2 = "ц"
    Case "d"
        Tmp1 = "д"
    Case "e"
        Tmp1 = "е"
    Case "f"
        Tmp1 = "ф"
    Case "g"
        Tmp1 = "г"
        Tmp2 = "ж"
    Case "h"
        Tmp1 = "х"
    Case "i"
        Tmp1 = "и"
    Case "j"
        Tmp1 = "ж"
    Case "k"
        Tmp1 = "к"
    Case "l"
        Tmp1 = "л"
        Tmp2 = "1"
    Case "m"
        Tmp1 = "м"
    Case "n"
        Tmp1 = "н"
        Tmp2 = "п"
    Case "o"
        Tmp1 = "о"
        Tmp2 = "0"
    Case "p"
        Tmp1 = "п"
        Tmp2 = "р"
    Case "q"
        Tmp1 = ""
    Case "r"
        Tmp1 = "р"
    Case "s"
        Tmp1 = "с"
    Case "t"
        Tmp1 = "т"
    Case "u"
        Tmp1 = "и"
        Tmp2 = "у"
        Tmp3 = "ю"
    Case "v"
        Tmp1 = "в"
    Case "w"
        Tmp1 = "в"
    Case "x"
        Tmp1 = "х"
    Case "y"
        Tmp1 = "у"
        Tmp2 = "ю"
    Case "z"
        Tmp1 = "з"
' для случая не слишком грамотных (вместо "сделать" - "зделать", и т.п.)
        Tmp2 = "с"
End Select


[alibek]

qwertyhp, не нужно советовать такой код. Он глупый и неграмотный. Ну и в целом бесполезный для практического применения.

[qwertyhp]

2alibek: Мы все будем очень признательны за умный и грамотный код, полезный для практического применения, который будет решать задачу коррекции очепяток и которым Вы, не сомневаюсь, в самое ближайшее время сможете нас порадовать.
Просто переведите Ваш комментарий с русского на MS Visual Basic 6.0, и всё - "звёздочки в студию!" (ах, да, всего-то два ряда...) А я - я таки просто выложил АЛГОРИТМ коррекции (как я его вижу), а не писал Пятое Евангелие.

[Roman Koff]

2qwertyhp - вероятно никогда не слышал о таком известном пакете как ABBYY FineReader (и вообще о технологии Optical Character Recognition) ...

[jangle]

Список улиц Москвы выкладываю в архиве. Других объектов нет, но посмотрю в Сети.

За список улиц большое спасибо! Это действительно ценная и нужная информация

[MIT]

Странно, что вас, вероятно, не удивляет - как это Microsoft сразу не выпустила Windows XP для IBM XT, а начала с Windows 1.0? Вот точно также и в других случаях. От простого - к сложному.

А вот и не правда. Они уже тогда написали и XP и Win7, просто компьютеров, на которых оно бы запустилось тогда прсто не было. Начали они, собственно, с написания NT4, но поскольку работать системе было не на чем, её урезАли и урезАли. В итоге урезали до Windows 1.0, и система наконец запустилась. А исходный, но немного доработанный, вариант NT4 смог запуститься только на компьютерах в районе 2000ого года, откуда и название.
Так-то.

Вот транслит плюс ошибки набора:

А зачем этот код? Я что-то не уловил к чему оно тута...

[qwertyhp]

Уф-ф-ф... Начнём, пожалуй, с MIT.
По поводу NT4.
"...Windows NT была разработана «с нуля», развивалась отдельно от других ОС семейства Windows (Windows 3.x и Windows 9x)..."
Windows NT 3.1 - первый выпуск 27 июля 1993
Windows NT 3.5 (Daytona) - первый выпуск 21 сентября 1994
Windows NT 3.51 - первый выпуск 30 мая 1995
Windows NT 4.0 - первый выпуск 29 июля 1996 (SP6a - 30 ноября 1999)

За подробностями милости просим на
http://ru.wikipedia.org/wiki/Windows_NT_4
http://ru.wikipedia.org/wiki/Windows_NT
К тому же, Windows х.x - это не ОС, а графическая оболочка - и без DOS не стартует.
Да и из общей эрудиции - посмотрите на адресацию памяти и жестких дисков (а 640 кБайт оперативки долгое время были пределом фантазии, считалось, что дальше 386-х машин конфиг х86 вообще не пойдёт!) - о каких Windows XP или Windows 7 тогда могла идти речь!? Windows XP - это сервис того ОБЩЕДОСТУПНОГО компьютерного железа, о котором в те времена вообще не было даже глюков! Не было стандартов, ничего не было!!! Уважаемый MIT, ну что ж Вы так...
Далее.
"...А зачем этот код? Я что-то не уловил к чему оно тута..."
Он тута, потому что ЧИТАЙ в первом сообщении - "...все слова могут быть записаны с ошибками и вперемешку кириллицей и латиницей."
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
2Roman Koff: Их бин русиш ферштейн нихт. Не андерстенд, то бишь. Есть замечания по существу - на MS Visual Basic 6.0, please.
О "Optical Character Recognition" - в курсе. Но алгоритмы (а они патентованные), как правило, стоят денег и на дороге не валяются, а здесь надо сделать СВОЮ программу (или комплект программ), а не юзать ломаный ABBYY FineReader.
К тому же я так и не понял - задача оптического распознавания стоИт, или нет. В любом случае - она интересна, поэтому будет решаться.

[Roman Koff]

Расслабь свои члены, это была шутка ...

[jangle]

Для сравнение адресов, необходимо привести их в промежуточный формат, чтобы отсечь 10%-20% ошибок ввода текста.
Вот пример функции.

Код: Выделить всё

Private Function IL_CODE(ByVal txt As String) As String
    Dim out_str As String
    out_str = Replace(txt, Chr$(32), "")
    out_str = Replace(out_str, "-", "")
    out_str = Replace(out_str, ",", "")
    out_str = Replace(out_str, ".", "")
    out_str = Replace(out_str, Chr$(34), "")
    out_str = Replace(out_str, "_", "")
    out_str = Replace(out_str, "(", "")
    out_str = Replace(out_str, ")", "")
    out_str = Replace(out_str, "«", "")
    out_str = Replace(out_str, "»", "")
    out_str = Replace(out_str, "¹", "N") '<-- тут номер заменяем на N
    IL_CODE = LCase$(out_str)
End Function

[Antonariy]

Если уничтожить все пробелы, то количество ошибок только увеличится.

[jangle]

Если уничтожить все пробелы, то количество ошибок только увеличится.

Это еще почему?

[Antonariy]

Потомучтогладиолус.
улЛенинад26

[jangle]

Потомучтогладиолус.
улЛенинад26

Подумай лучше...

Код: Выделить всё

IL_CODE("ул. Ленина д. 26") -> улленинад26
IL_CODE("ул  Ленина Д 26")  -> улленинад26
IL_CODE("УЛ      ЛЕНИНА   Д 26")  -> улленинад26

[Antonariy]

И чем же "улленинад26" лучше "ул ленина д 26"? Про знаки препинания вопросов нет.

[Денис]

+1
иещекактысплититьстрокубудешьесливнейнеостанетсяващениодногоразделителя?
асплититьстрокупридетсявсеравнонаследующемшаге.

Есть смысл рекурсивно заменить два пробела на один. Например, так:

Код: Выделить всё

    do while not outstr = txt
        out_str = Replace(txt, "  ", " ")
    loop

Или регэкспами, но с ними отец русской демократии не знаком.