github-featured / unstructured-io--unstructured

发布

RSS 订阅源

0.10.25 82c8adba3f

比较
fix: split-chunks appear out-of-order (#1824)

frostbyte_neo 发布于 2023-10-21 01:37:34 +00:00
Executive Summary. Code inspection in preparation for adding the
chunk-overlap feature revealed a bug causing split-chunks to be inserted
out-of-order. For example, elements like this:
```
Text("One" + 400 chars)
Text("Two" + 400 chars)
Text("Three" + 600 chars)
Text("Four" + 400 chars)
Text("Five" + 600 chars)
```
Should produce chunks:
```
CompositeElement("One ...")           # (400 chars)
CompositeElement("Two ...")           # (400 chars)
CompositeElement("Three ...")         # (500 chars)
CompositeElement("rest of Three ...") # (100 chars)
CompositeElement("Four")              # (400 chars)
CompositeElement("Five ...")          # (500 chars)
CompositeElement("rest of Five ...")  # (100 chars)
```
but produced this instead:
```
CompositeElement("Five ...")          # (500 chars)
CompositeElement("rest of Five ...")  # (100 chars)
CompositeElement("Three ...")         # (500 chars)
CompositeElement("rest of Three ...") # (100 chars)
CompositeElement("One ...")           # (400 chars)
CompositeElement("Two ...")           # (400 chars)
CompositeElement("Four")              # (400 chars)
```
This PR fixes that behavior that was introduced on Oct 9 this year in
commit: f98d5e65 when adding chunk splitting.

Technical Summary

The essential transformation of chunking is:
```
elements          sections              chunks
List[Element] -> List[List[Element]] -> List[CompositeElement]
```
1. The sectioner (_split_elements_by_title_and_table()) groups
  semantically-related elements into sections (List[Element]), in the
  best case, that would be a title (heading) and the text that follows it
  (until the next title). A heading and its text is often referred to as a
  section in publishing parlance, hence the name.
2. The chunker (chunk_by_title() currently) does two things:
3. first it consolidates the elements of each section into a single
  ConsolidatedElement object (a "chunk"). This includes both joining the
  element text into a single string as well as consolidating the metadata
  of the section elements.
4. then if necessary it splits the chunk into two or more
  ConsolidatedElement objects when the consolidated text is too long to
  fit in the specified window (max_characters).
Chunk splitting is only required when a single element (like a big
paragraph) has text longer than the specified window. Otherwise a
section and the chunk that derives from it reflects an even element
boundary.

chunk_by_title() was elaborated in commit f98d5e65 to add this
"chunk-splitting" behavior.

At the time there was some notion of wanting to "split from the end
backward" such that any small remainder chunk would appear first, and
could possibly be combined with a small prior chunk. To accomplish this,
split chunks were inserted at the beginning of the list instead of
appended to the end.

The chunked_elements variable (List[CompositeElement]) holds the
sequence of chunks that result from the chunking operation and is the
returned value for chunk_by_title(). This was the list
"split-from-the-end" chunks were inserted at the beginning of and that
unfortunately produces this out-of-order behavior because the insertion
was at the beginning of this "all-chunks-in-document" list, not a
sublist just for this chunk.

Further, the "split-from-the-end" behavior can produce no benefit
because chunks are never combined, only elements are combined (across
semantic boundaries into a single section when a section is small) and
sectioning occurs prior to chunking.

The fix is to rework the chunk-splitting passage to a straighforward
iterative algorithm that works both when a chunk must be split and when
it doesn't. This algorithm is also very easily extended to implement
split-chunk-overlap which is coming up in an immediately following PR.
```
# -- split chunk into CompositeElements objects maxlen or smaller --
text_len = len(text)
start = 0
remaining = text_len

while remaining > 0:
    end = min(start + max_characters, text_len)
    chunked_elements.append(CompositeElement(text=text[start:end], metadata=chunk_meta))
    start = end - overlap
    remaining = text_len - end
```
Forensic analysis
The out-of-order-chunks behavior was introduced in commit 4ea71683 on
10/09/2023 in the same PR in which chunk-splitting was introduced.

Co-authored-by: Shreya Nidadavolu shreyanid9@gmail.com
Co-authored-by: shreyanid 42684285+shreyanid@users.noreply.github.com
下载附件
- 源代码 (ZIP)
- 源代码 (TAR.GZ)

0 发布 249 Git 标签

fix: split-chunks appear out-of-order (#1824)