diff --git a/tools/releasetools/common.py b/tools/releasetools/common.py
index 9d58954..34c334e 100644
--- a/tools/releasetools/common.py
+++ b/tools/releasetools/common.py
@@ -772,6 +772,14 @@
   certmap = {}
   compressed_extension = None
 
+  # META/apkcerts.txt contains the info for _all_ the packages known at build
+  # time. Filter out the ones that are not installed.
+  installed_files = set()
+  for name in tf_zip.namelist():
+    basename = os.path.basename(name)
+    if basename:
+      installed_files.add(basename)
+
   for line in tf_zip.read("META/apkcerts.txt").split("\n"):
     line = line.strip()
     if not line:
@@ -796,6 +804,10 @@
       else:
         raise ValueError("failed to parse line from apkcerts.txt:\n" + line)
       if this_compressed_extension:
+        # Only count the installed files.
+        filename = name + '.' + this_compressed_extension
+        if filename not in installed_files:
+          continue
         # Make sure that all the values in the compression map have the same
         # extension. We don't support multiple compression methods in the same
         # system image.