Sistemas de Recuperação
da Informação
Parte IV
Multimídia
MIDIAS
Principais estruturas:
• Textos – linguagem natural
• Hipertextos - caminhamento
• Textos estruturados - esquema
• textos marcados – esquema
• multimidia (dados digitais de diferentes midias):
• texto
• som (linguagem falada, música, ruídos)
• imagens (fotos, pinturas, mapas, diagramas, tabelas)
• vídeo – sequência síncrona dos anteriores
(filmes, animações de imagens)
•
MULTIMIDIA
Hipertextos:
Um grafo dirigido de textos e sub-textos.
Cada aresta aponta ou par um texto ou para um subtext.
Fonte pode ser um
• documento,
• parágrafo,
• palavra
• bloco de n caracteres
EXEMPLO: Um Índice Remissivo (a fonte é uma página)
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
EXEMPLO:
Texto 1 (t1):
Integridade declarativa ou implícita: são condições inseridas no próprio esquema
conceitual da aplicação desenvolvida. Isto é um dos objetivos de um modelo
semântico de dados, de captar o máximo possível de condições de consistência na
própria estrutura do esquema conceitual. Existem várias formas de expressar estas
condições:
1) Esquema, tipos, subtipos: os próprios conceitos de classes e subclasses, atributos e
domínios, impõem restrições ao tipo e formato dos dados a serem armazenados no
banco de dados;
2) Outras hierarquias: também as hierarquias de agregação e agrupamento, assim
como outras que porventura poderão ser desenvolvidas, permitem descrever um
comportamento especial dos elementos envolvidos.
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
Dicionário de termos com lista de documentos
Integridade declarativa
implícita
condições
esquema conceitual
aplicação
objetivos
modelo semântico de dados
condições de consistência
estrutura
esquema conceitual
condições
Esquema
tipos
Subtipos
Classes
Subclasses
Atributos
Domínios
Restrições
Tipo
Formato
Dados
Armazenados
banco de dados;
Hierarquias
Hierarquias
Agregação
Agrupamento
Comportamento.
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
Dicionário de termos com lista de documentos
Integridade declarativa
Integridade
implícita
condições (3)
esquema conceitual (2)
aplicação
objetivos
modelo semântico de dados
condições de consistência
estrutura
Esquema (3)
Tipos (2)
Subtipos
Dados (3)
Classes
Subclasses
Atributos
Domínios
Restrições
Formato
Armazenados
banco de dados
Hierarquias (2)
Agregação
Agrupamento
Comportamento.
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
Texto 2 (t2):
Integridade não-declarativa: nenhum modelo de dados é suficientemente rico
para poder captar todas as restrições de integridade de uma aplicação complexa.
Certas restrições não podem ser dadas de forma declarativa nas estruturas de dados e
precisam ser expressas explicitamente de alguma forma. Isto pode acontecer de
quatro maneiras distintas:
1) Por meio de invariantes ou asserções, que permitem descrever as restrições de
integridade como fórmulas ou expressões em uma linguagem específica, que serão
verificadas sempre que necessário.
2) Por meio de pré- e pós-condições associadas às operações (vide parágrafo
seguinte);
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
Dicionário de termos com lista de documentos
Integridade não-declarativa
modelo de dados
restrições de integridade
aplicação complexa
Restrições
forma declarativa
estruturas de dados
Expressas
explicitamente
Invariantes
asserções
restrições de integridade
Fórmulas
Expressões
linguagem específica
pré-condições
pós-condições
operações
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
Dicionário de termos com lista de documentos
Integridade não-declarativa
Integridade (3)
modelo de dados
restrições de integridade (2)
aplicação complexa
Restrições (3)
forma declarativa
estruturas de dados
Dados (2)
Expressas
explicitamente
Invariantes
asserções
Fórmulas
Expressões
linguagem específica
pré-condições
pós-condições
Condições (2)
operações
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
Dicionário de termos com lista de documentos
T1:
T2:
condições (3)
Dados (3)
Esquema (3)
esquema conceitual (2)
Hierarquia (2)
Tipos (2)
Condições (2)
Dados (2)
Integridade (3)
restrições de integridade (2)
Restrições (3)
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
Dicionário de termos ponderados com lista de documentos
Condições
T1,3
Dados
T1,3
esquema
T1,3
Esquema conceitual
T1,2
hierarquia
T1,2
Restrições de integridade
T2,2
tipos
T1,2
T2,2
T2,2
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
Dicionário de termos ponderados com lista de documentos
considerando a posição
Condições
T1,3 (1-6;2-18; 3-7)
Dados
T1,3 (2-11; 4-21; 4-28)
esquema
T1,3 (1-10; 2-26; 4-1)
Esquema conceitual
T1,2
hierarquia
T1,2
Restrições de integridade
T2,2
tipos
T1,2
T2,2 (5-4;5-7)
T2,2
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
Dicionário de termos ponderados com lista de documentos
considerando a posição
1.Condições
T1,3 (1-6;2-18; 3-7)
2.Dados
T1,3 (2-11; 4-21; 4-28)
3.Esquema (-4, -2, ~7)
T1,3 (1-10; 2-26; 4-1)
4.Esquema conceitual(+3)
T1,2
5.hierarquia
T1,2
6.Restrições de integridade (~1)
7.tipos(~3)
T2,2
T1,2
T2,2 (5-4;5-7)
T2,2
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
Trie dos índices:
C
T1,3
D
T1,3
T2,2
T2,2
T1,3
esquema
c
T1,2
h
T1,2
R
T2,2
t
T1,2
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
Incremento dos índices:
1. Termo `condições`:
2. Acréscimo de `consistência` em T1:
C
T1,3
o
n
T2,2
d
s
T2,1
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
Árvore de sufixos:
C
T1,3
o
n
d
s
d
1
c
T2,2
T2,1
T1,3
T2,2
3
s
T2,1
ESTRUTURAS DE ARQUIVOS
Arquivos invertidos :
Vantagens
• cada termo só aparece uma vez
• busca por proximidade
• facilidade de associar pesos, posições
Desvantagens
• muita redundância nas referências aos documentos
•
ESTRUTURAS
DE disponível
ARQUIVOS
A crescente quantidade
de informação
na Web trás problemas
desafiadores relacionados à recuperação de informação. Atualmente a maior
parte do conteúdo disponível na Web está escrito em inglês, porém estudos
EXERCÍCIO
recentes demonstram que o crescimento da quantidade de informação
disponível na Web é maior para outros idiomas, que não o inglês. Nesse
contexto a cada dia aumenta a necessidade por sistemas capazes de
recuperar informação sem levar em consideração o idioma no qual a
informação esteja expressa.
Além da Web, vários outros sistemas de informação que lidam com
documentos, tal como bibliotecas digitais e convencionais, jornais,
documentos jurídicos, entre outros, vem tendo um significativo aumento na
quantidade de informação que pode estar expressa em uma grande
variedade de idiomas diferentes.
A recuperação de informação multilíngüe vem sendo tema de pesquisas já
há bastante tempo e ao longo desse tempo ótimos resultados vêm sendo
obtidos pelos pesquisadores da área. Muitos pesquisadores, inclusive,
acreditam que o problema de recuperação de informação multilíngüe já está
resolvido [15].
ESTRUTURAS DE ARQUIVOS - Textos integrais
N-Gramas
Divide o texto em pedaços de tamanho fixo (n):
Bigramas:
Di iv vi id de o te ex xt to em pe ed da aç ço os …
Trigramas:
Div ivi vid ide o tex ext xto em ped eda daç ços …
Com marcadores de palavras:
#Div ivi vid ide# #o# #tex ext xto# …
ESTRUTURAS DE ARQUIVOS
N-Gramas
Aplicaçoes
•
•
•
•
•
Criptografia
Correção de erros de grafia
Compressão de textos
Manipulação de índices
Recuperação de textos integral
ESTRUTURAS DE ARQUIVOS
N-Gramas
erros de grafia:
Erros típicos:
• Commputer (letra a mais)
• Cmputer (letra a menos)
• Comptuer (letras trocadas)
• Cumputer (letra errada)
Regras de substituição:
• omm mmu ~ omu
• cmp ~ com omp
• mpt ptu ~ mpu put
Cum ump ~ com omp
ESTRUTURAS DE ARQUIVOS
Árvores PATRICIA (PAT trees e PAT arrays)
(Practical Algorithm To Retrieve Information Coded In Alphanumerics)
Também chamado de árvore ou array de sufixos.
Um texto é considerado como uma longa cadeia de
caracteres.
Cada posição desta cadeia é o começo de um sufixo
(semi-infinito) do texto
ESTRUTURAS DE ARQUIVOS
Árvores PATRICIA (PAT trees e PAT arrays)
“Um texto é considerado como uma longa cadeia de caracteres.”
Um texto é considerado como uma longa cadeia de caracteres.
m texto é considerado como uma longa cadeia de caracteres
texto é considerado como uma longa cadeia de caracteres
exto é considerado como uma longa cadeia de caracteres
ESTRUTURAS DE ARQUIVOS
Árvores PATRICIA (PAT trees e PAT arrays)
Sufixos significativos = pontos de indexação:
Um texto é considerado como uma longa cadeia de caracteres.
1
2
3
4
5
texto é considerado como uma longa cadeia de caracteres.
considerado como uma longa cadeia de caracteres
longa cadeia de caracteres
cadeia de caracteres
caracteres
ESTRUTURAS DE ARQUIVOS
Árvores PATRICIA (PAT trees e PAT arrays)
Representação
Um texto é considerado como uma longa cadeia de caracteres.
1
4
10
34
Trie
4
10
t
40
o
d
c
a
r
l
34
50
40
50
ESTRUTURAS DE ARQUIVOS
Árvores PATRICIA (PAT trees e PAT arrays)
Representação
Um texto é considerado como uma longa cadeia de caracteres.
1
4
10
Array ordenado
Com supra índice-2
34
40
40 | 50 | 10 | 34 | 4 |
ca | co | lo | te |
50
ESTRUTURAS DE ARQUIVOS
Árvores PATRICIA (PAT trees e PAT arrays)
Aplicações
•
•
•
•
•
•
Índice remissivo (supra –indice-n)
Pesquisa por prefixos
Pesquisa de proximidade entre dois strings
Pesquisa por abrangências léxicas
p.ex. “abc” ... “acc” inclui “abra”, “acacia” mas não “acrimonioso”
Frequências de textos
Pesquisa por expressões regulares
Consultas: p.ex.
os trigrams mais frequentes
~
a maior sub-árvore a partir do nível 3 da raíz
ESTRUTURAS DE ARQUIVOS
Arquivos Assinatura
É uma forma extremamente compacta de caracterizar
um texto por meio de uma “assinatura”.
Assinatura = um bitstring que caracteriza uma
palavra-chave  um bloco  um documento
X uma consulta
ESTRUTURAS DE ARQUIVOS
Arquivos Assinatura
Palavra
Assinatura
Computer
Science
Graduate
Students
Study
0001 0110 0000 0110
1001 0000 1110 0000
1000 0101 0100 0010
0000 0110 0110 0100
0000 0110 0110 0100
Assinatura do bloco
1001 0111 1110 0110
Constante: número de bits 1 por termo (=5)
ESTRUTURAS DE ARQUIVOS
Arquivos Assinatura – Blocos de 5 palavras
A crescente quantidade de informação
disponível na Web trás problemas desafiadores
relacionados à recuperação de informação.
Atualmente a maior parte do
conteúdo disponível na Web está
escrito em inglês, porém estudos
recentes demonstram que o crescimento
da quantidade de informação disponível
na Web é maior para
outros idiomas, que não o inglês.
0001 0110 0000 0110
1001 0000 1110 0000
1001 0111 0100 0110
0000 0000 0000 0000
0010 0110 0010 0100
0000 0110 0110 0100
0000 0000 0000 0000
0001 0110 0000 0110
1001 0000 1110 0000
0010 0110 0110 0100
Palavra
Informação
Web
Recuperação
Inglês
Idioma(s)
1011 0111 1110 0110
Assinatura
0001 0110 0000 0110
1001 0000 1110 0000
1000 0101 0100 0010
0000 0110 0110 0100
0010 0110 0010 0100
Assinatura do documento 1001 0111 1110 0110
ESTRUTURAS DE ARQUIVOS
Arquivos Assinatura - Consultas
A crescente quantidade de informação
disponível na Web trás problemas desafiadores
relacionados à recuperação de informação.
Atualmente a maior parte do
conteúdo disponível na Web está
escrito em inglês, porém estudos
recentes demonstram que o crescimento
da quantidade de informação disponível
na Web é maior para
outros idiomas, que não o inglês.
0001 0110 0000 0110
1001 0000 1110 0000
1001 0111 0100 0110
0000 0000 0000 0000
0010 0110 0010 0100
0000 0110 0110 0100
0000 0000 0000 0000
0001 0110 0000 0110
1001 0000 1110 0000
0010 0110 0110 0100
1011 0111 1110 0110
Consulta: “Recuperação na web”
Web
Recuperação
1001 0000 1110 0000
1000 0101 0100 0010
Assinatura da consulta
1001 0101 1110 0010
1001 0101 1110 0010
ESTRUTURAS DE ARQUIVOS
Hipertextos
Um Hypertexto é um grafo dirigido de textos e pontos no texto.
Cada nó é um texto e cada aresta aponta de um ponto em
um texto a outro ponto em um texto.
Na Internet o padrão é HTML
Um hiperlink é dado por
<a href=“<url>”>texto</a>
ESTRUTURAS DE ARQUIVOS
Hipertextos
EXEMPLO:
HTML
ESTRUTURAS DE ARQUIVOS
Hipertextos
Sistema que combina Pesquisa com browsing:
WebGlimpse
Questões:
• desprezar hiperlinks
• como considerar hiperlinks locais
• em que profundidade considerar hiperlinks externos
(ciclos, cadeias ‘infinitas’)
ESTRUTURAS DE ARQUIVOS
EXERCÍCIO
Para as palavras chave do exercício anterior criar
assinaturas para as palavras chave e usar
os parágrafos como unidades e criar uma assinatura
para cada parágrafo.
Considere as consultas:
• “Web multilingue”
• “idiomas na Web”
Quais textos serão retornados?